aman_naughty's blog

Binary Search One Last Time
By aman_naughty, history, 5 years ago, In English

Can someone please help me in binary search. I am confused whether to use

--> l=0 , h = arr.size()-1 and m = (l+h)/2 and while(l<h)

--> l=0 , h = arr.size() and m = (l+h+1)/2 and while(l<h)

--> l=0 , h = arr.size()-1 and m = l+(h-l)/2 and while(l<h)

--> l=0 , h = arr.size()-1 and m = (l+h)/2 and while(l<=h)

It seems that in some cases some of the above give TLE. Can some experienced community member help me which I should use .

I think many of the beginners face this issue while implementing binary search . A little help would be appreciated

So basically there are confusion regarding

while(l<h) or while(l<=h) or while(h-l>1)

m=(l+h+1)/2 or m=l+(h-l)/2 or m=(l+h)/2

h=arr.size() or h=arr.size()-1

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
5 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Just think what exactly you want to happen for intervals of size 1, 2 or 3.

You can watch my video here, https://www.youtube.com/watch?v=GU7DpgHINWQ.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In the description section of your video you recommended solving leetcode binary search problems. Actually I was solving this problem from leetcode : problem

    In the discuss forum on leetcode : link the great StefanPochmann explained a rather new solution which I am unable to understand. Can you help me with that. Also nice video:)

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      It's something unique for this problem so you won't use it in other problems anyway ;p the important thing is to understand when you should go to the right, when to the left.

      What he does is he imagines that one part of the sequence is changed into -INF or +INF what tells you to go right or left respectively.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Literally the best video on binary search .

    → Reply
»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Here is what I do:

int start = 0;
int end = n - 1;

while (start <= end) {
    int mid = (start + end) / 2;
    if (check(mid)) LOGIC1
    else LOGIC2
}

The key is to think about what your binary searched values will look like (TTTTTFFFFFF? or opposite) and then about which one you want (first occurrence of T? last occurrence of F?) which mostly depends on the problem and how you defined true/false values. Then you can select either start = mid + 1 or end = mid — 1 in the LOGIC places I wrote. I select these by thinking about what happens at the end case (the destination where we have either TF or FT transition).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't think that makes a difference.

PS: I wonder if the second implementation is correct?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What I do is one of 2 of the following, depending on the problem i'm solving:

int lo=begin, hi=end; //the range(inclusive)
while (lo<hi)
{
    int mid=(lo+hi)/2;
    if (f(mid)) lo=mid+1; // can also be !f(mid) if the problem requires that
    else hi=mid;
}
//lo=hi=result

or

int lo=begin, hi=end; //the range(inclusive)
while (lo<hi)
{
    int mid=(lo+hi+1)/2;
    if (f(mid)) lo=mid; // can also be !f(mid) if the problem requires that
    else hi=mid-1;
}
//lo=hi=result

So I start by writing $$$mid=(lo+hi)/2$$$ and when i write the rest of the while loop I add a +1 if I have $$$hi=mid-1$$$.

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it 
while(low <= high)
{
   mid = (low + high ) / 2. /// if u use long long .
   else mid = (low + (high &mdash; low)/2) /// if int as it would be safe. 
   do something with mid. 
   store the result of mid if needed.
   then either low = mid + 1 , or high = mid -1 .
}
→ Reply