Yet Another Trivial Binary Search Implementation

Revision en24, by jeqcho, 2021-02-19 17:05:48

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

Tags #binary search

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en24 English jeqcho 2021-02-19 17:05:48 26
en23 English jeqcho 2021-02-19 16:59:06 46
en22 English jeqcho 2021-02-19 16:56:04 10 Tiny change: 'he answer (`lef-1`) is the la' -> 'he answer is the la'
en21 English jeqcho 2021-02-19 16:47:18 438 Applied improvements thanks to [user:sergei_popov]
en20 English jeqcho 2021-02-19 09:59:01 0 (published)
en19 English jeqcho 2021-02-19 09:58:24 33 Tiny change: '08687]\n\nIndee' -> '08687]\n\n- 237C [submission:107914994]\n\nIndee'
en18 English jeqcho 2021-02-19 09:55:01 73
en17 English jeqcho 2021-02-19 09:54:14 3
en16 English jeqcho 2021-02-19 09:53:34 4 Tiny change: 't problem C2)\n\n- [' -> 't problem 1486C2)\n\n- ['
en15 English jeqcho 2021-02-19 09:53:10 7 Tiny change: '107906435]\n\n- [sub' -> '107906435] (367C)\n\n- [sub'
en14 English jeqcho 2021-02-19 09:52:46 7 Tiny change: '107908687]\n\nIndeed' -> '107908687] (604B)\n\nIndeed'
en13 English jeqcho 2021-02-19 09:49:12 28 Tiny change: 'nd `rig`. If $a$ i' -> 'nd `rig`. `lef` is set out of bounds. If $a$ i'
en12 English jeqcho 2021-02-19 09:46:20 22
en11 English jeqcho 2021-02-19 09:43:39 1
en10 English jeqcho 2021-02-19 09:42:50 80
en9 English jeqcho 2021-02-19 09:33:43 30
en8 English jeqcho 2021-02-19 09:31:45 94 Tiny change: ',a+n,-1)-a; // get i' -> ',a+n,-1)-a-1; // get i'
en7 English jeqcho 2021-02-19 09:24:13 264 Tiny change: 'e. If `a` can be co' -> 'e. If `a` is available or can be co'
en6 English jeqcho 2021-02-19 09:16:14 8 Tiny change: '`mid+1`, `lef+1` etc.\n\' -> '`mid+1`, `rig-1` etc.\n\'
en5 English jeqcho 2021-02-19 08:24:52 258 Tiny change: '0, rig = n-1;\nwhile(l' -> '0, rig = n;\nwhile(l'
en4 English jeqcho 2021-02-19 08:04:27 316 Tiny change: ' $\log N$.' -> ' $\log N$. Thanks to [user:marvenlee] for inspiring this blog.'
en3 English jeqcho 2021-02-19 07:42:06 3
en2 English jeqcho 2021-02-19 07:40:07 1015 Tiny change: '$a=[1,1,1,1,0,0,0]$\n' -> '$a=[1,1,1,$**$1$**$,0,0,0]$\n'
en1 English jeqcho 2021-02-19 07:15:15 157 Initial revision (saved to drafts)