rum3r's blog

Problem with Binary Search!
By rum3r, 4 years ago, In English

Can someone point out the error in this code -> PROBLEM
I am assuming there's something wrong with my binary search.
This is the implementation I normally use. In case if someone could suggest something better.

And also if someone can give me a link to the blogs explaining different implementation's of binary search, it would be very helpful. I think there were some blogs regarding this topic. I can't remember properly during round Div. 2 (703).

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

Comments Comments (3)
| Write comment?
»
4 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

There are twp ways of writing binary search that I know of. In the first, the current search range is represented by [lo, hi]. If m = (l + r) / 2, then we have two cases to continue to check:

  • check towards smaller numbers: then we know the search range will be [lo, m — 1] (no need to include m again)

  • check towards larger numbers: then we know the search range will be [m + 1, hi]

As long as [lo, hi] is non-empty, we continue searching, so the condition in the while loop is while (lo <= hi).

The other way is when the search range is represented by [lo, hi). For the two cases above, they can be represented as:

  • check towards smaller numbers: new range will be [lo, m)

  • check towards larger numbers: new range will be [m, hi)

As long as [lo, hi) is non-empty, we continue searching, so the condition in the while loop is while (lo < hi).

You can use whichever implementation that you wish, but you have to make sure that you set the boundaries to the correct values.

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

    $$$Thanks For Replying!$$$
    I think this is a typo $$$[m + 1, hi)$$$ $$$->$$$ $$$[m, hi)$$$
    Now, I have a question let's say I want to find the max element $$$<= x$$$ .
    Now if I write something like this.

    int l = 0, h = n;
while(h-l > 1) {
    int m = (l+h) >> 1;
    if(a[m] <= x)
        l = m;
    else
        h = m-1;
}
return l;

    Now, as far as the invariant and my small brain goes, $$$l$$$ should always hold element $$$<= x$$$ and $$$h$$$ should hold element $$$> x$$$. But as we are assigning $$$h = m-1$$$. There may be a case where m is at the boundary(first element $$$> x$$$). Then $$$h$$$ would have been assigned $$$<= x$$$ value which destroys the invariant.
    And also when to use $$$while(h>l)$$$ or $$$while(h-l>1)$$$ is there any difference ?
    $$$while(h>l)$$$ was not working so I used $$$while(h-l>1).$$$

    My usual implementation looks like this. I modify $$$l$$$ and $$$h$$$ accordingly to the problem. Is there anything wrong in this ?

    int l = 0, h = n;
while(h-l > 1) {
    int m = (l+h) >> 1;
    if(a[m] <= x)
        l = m;
    else
        h = m;
}
return l;


    Damn, this $$$latex..$$$

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

      Yes, that was an error on my part. I have fixed it.

      The way that I usually do binary search uses an ans variable which is initially set at -1. If the current value of m is "valid" (<= x in this case), then we can set the variable value at this stage. By doing this, you can deal with the case that there is no solution within the search range. I'm not very familiar with setting both l and h to m, but it at least does not work conceptually with the idea that [l, h) is the current search space (however there could be another analogy where it would work, and it if you have used it before, then why doubt that it works). However, this is why I am unsure about the boundary condition. Thinking about it, it looks like it represents the interval (l, h), which matches the while loop condition as well. However, your starting values wouldn't work then.

      → Reply