jeqcho's blog

By jeqcho, history, 3 years ago, In English

These might be trivial for most users, but if you are like me, who sometimes confuse on when to use mid+1, rig-1 etc, here is a reliable method after considering many different implementation variants.

To find the index of the rightmost $$$1$$$ in a monotonically decreasing function, for example $$$a=[1,1,1,1,0,0,0]$$$

Define check(i) to return true when $$$a[i]=1$$$, false otherwise.

int lef = 0, rig = n-1;
int ans = -1;
while(lef <= rig) {
	int mid=(lef + rig)/2;
	if(check(mid)){
		lef = mid+1;
		ans = mid;
	} else {
		rig = mid-1;
	}
}

The answer is the last valid mid. Make sure that lef and rig are in bounds. If $$$a$$$ is available or can be computed efficiently, you can instead do

F0R(i,n)a[i]*=-1;
int ans = upper_bound(a,a+n,-1)-a-1; // get index of rightmost 1

Careful if $$$1$$$ doesn't exist in $$$a$$$.

To find the index of the leftmost $$$1$$$ in a monotonically increasing function, for example $$$a=[0,0,0,0,1,1,1]$$$

In a similar way,

int lef = 0, rig = n-1;
int ans = -1;
while(lef <= rig) {
	int mid=(lef + rig + 1)/2;
	if(check(mid)){
		rig = mid-1;
		ans = mid;
	} else {
		lef = mid+1;
	}
}

Notice the ceiling in the definition of mid. This is to handle rig-lef equals one. If $$$a$$$ is available or can be computed efficiently, you can instead do

int ans = lower_bound(a,a+n,1)-a; // get index of leftmost 1

Careful if $$$1$$$ doesn't exist in $$$a$$$.

You can then solve most problems by implementing your own definition of check(). Time complexity is the time complexity of your check() function times $$$\log n$$$. Thanks to marvenlee for inspiring this blog.

Usage examples:

Indeed, there are many other ways of implementing binary search, check out pllk's blog.

UPD Applied improvements thanks to sergei_popov

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

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by jeqcho (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Thank you! I also mess up bounds all the time and end up wasting lot of time fixing edge cases.

Things like lo < hi or lo <= hi? lo = mid + 1 or lo = mid? etc. always confuse me. I was trying to find answer to those but I am not sure I got it entirely.

In second version, is there any way to set left and right to bounds and still get the right answer?

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

    Yes, you can set left and right to bounds, but if so you must use lef<=rig in the condition. Careful, because it can stuck in an infinite loop. For example, take the edge case when lef equals rig and check(mid) is false, so it keeps calling rig=mid

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

      Now the updated version, thanks to sergei, does just that. Amazing community I must say

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

jeqcho, my implementation is similar to yours, a few other simplifications I like are :-

1) Store the temporary result at each step, this allows me to take advantages of the default code in point 2 and 3. Also this further helps in not having to think about whether final answer is right or right +/- 1 or left or left +/- 1.

2) I always like to go for left = mid + 1 and right = mid — 1. One less headache, now this is no longer problem specific but default code.

3) Due to point 1 again always am able to do left <= right.

So advantages, no worries of infinite loops, always have an answer, also since the basic are default it easier to apply to more complicated problems, where you no longer have to worry about binary search itself but rather can focus on the actual problem. That said always go for lower_bound and upper_bound where you can it saves time.

You can find another implementation here(I have tried to add all the points here itself). Also my 1486 C2 code as a further example.

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

    Really good suggestions. I learnt something from you. Thanks!

»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

You can avoid +1s altogether by maintaining check(r) != check(l).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by jeqcho (previous revision, new revision, compare).