Yet Another Trivial Binary Search Implementation
Difference between en20 and en21, changed 438 character(s)
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;↵
}↵
}↵
int ans = lef-1;↵
~~~~~↵
↵
Notice that the `mid` in `lef=mid+1` is always valid, so the answer (`lef-1`) is the last valid `mid`. Also notice the initial values of `lef` and `rig`. `rig` is set out of bounds~~~~~↵
↵
The answer (`lef-1`) is the last valid `mid`. 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 = -1, rig0, rig = n-1;↵
int ans = n-1;↵
while(lef <= rig) {↵
int mid=(lef + rig + 1)/2;↵
if(check(mid)){↵
rig = mid-1;↵
 ans = mid;↵
} else {↵
lef = mid+1;↵
}↵
}↵
int ans = rig+1;↵
~~~~~↵
↵
Notice the ceiling in the definition of `mid`. This is to handle `rig-lef` equals one. Again notice the initial values for `lef` and `rig`. `lef` is set out of bounds. 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 [user:marvenlee,2021-02-19] for inspiring this blog.↵
↵
Usage examples:↵
↵
- Recent problem 1486C2 [submission:10790142247036]↵
↵
- 367C [submission: 107906432055995]↵
↵
- 604B [submission:10790868745841]↵
↵
- 237C [submission:10791499446120]↵
↵
Indeed, there are many other ways of implementing binary search, check out [pllk's blog](https://codeforces.com/blog/entry/9901).↵
↵
**UPD** Applied improvements thanks to [user:sergei_popov,2021-02-19]

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)