taap_cader's blog

Binary Search conditions
By taap_cader, history, 3 years ago, In English

I know binary search but most of the time I gets confused how to find mid index and what to return low or high.
There are two while loop conditions:
1. while(low<high)
2. while(low<=high)
There are two ways to find mid element:
1. mid = (low+high)/2
2. mid = (low+high+1)/2
And then depending on the required condition we do low = mid+1 and right = mid or low = mid and right = mid-1 or something else. I know it's something keeping low always as our answer and returning that after while loop breaks and if high is always possible answer we return high. But I don't know clearly what to do when. Is there any logical way to do this stuff, I have try some combinations before getting right pair of conditions.
Thanks in advance.

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

Comments Comments (2)
| Write comment?
»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

There are two easy binary search approaches and one hard.

Easy 1.

Always maintain closed interval and the best answer outside this interval. Your template will be:

left = min_possible_answer
right = max_possible_answer
ans = null
while (left <= right) {
  mid = (left + right) / 2
  if (condition(mid)) {
    ...  
  } else {
    ...
  }
}
// ans contains null if there is no answer, otherwise it's the answer

Instead of dots:

  • Write left = mid + 1 and right = mid - 1 depending on your condition. It's always easy to see in which branch left or right border should be reassigned.
  • In one of the branches, also write ans = mid. Again, it's always easy to see in which one. If mid would be the better answer then ans, assign.

Easy 2.

It's called binary lifting. The template looks like this:

step = 1 << 30 // or 1LL << 60 or 1 << 20, just take the power of 2 which is > length_of_interval
ans = min_possible_answer - 1
while (step > 0) {
  if (isGood(ans + step)) {
    ans += step
  }
  step /= 2
}
// if ans is min_possible_answer - 1, there is no answer, otherwise it's the answer

I don't think this even requires any comments, it's just obvious. Absolutely no +/-1 errors.

Hard.

Let's wait when some red appears and writes it's the only true way. Who cares when you can literally make a mistake in EVERY expression.

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +3 Vote: I do not like it

I often use the second loop condition, while (low <= high), and the first way to find index of the middle element, mid = (low+high)/2. To update one of the limits, either low = mid+1 or high = mid-1, it is sufficient to keep in mind that the function $$$f$$$ computed at mid should be non-decreasing function, i.e. $$$f(mid-\delta) \leq f(mid) \leq f(mid+ \delta)$$$ for any positive value $$$\delta$$$.

→ Reply