Yet Another Trivial Binary Search Implementation

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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, rig~~0, 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:1079~~01422~~47036]↵
↵
- 367C [submission: 10~~790643~~2055995]↵
↵
- 604B [submission:1079~~08687~~45841]↵
↵
- 237C [submission:1079~~14994~~46120]↵
↵
Indeed, there are many other ways of implementing binary search, check out [pllk's blog](https://mirror.codeforces.com/blog/entry/9901).↵
↵
**UPD** Applied improvements thanks to [user:sergei_popov,2021-02-19]

Rev.	Кто	Когда	Δ	Комментарий
en24	jeqcho	2021-02-19 17:05:48	26
en23	jeqcho	2021-02-19 16:59:06	46
en22	jeqcho	2021-02-19 16:56:04	10	Tiny change: 'he answer (`lef-1`) is the la' -> 'he answer is the la'
en21	jeqcho	2021-02-19 16:47:18	438	Applied improvements thanks to [user:sergei_popov]
en20	jeqcho	2021-02-19 09:59:01	0	(published)
en19	jeqcho	2021-02-19 09:58:24	33	Tiny change: '08687]\n\nIndee' -> '08687]\n\n- 237C [submission:107914994]\n\nIndee'
en18	jeqcho	2021-02-19 09:55:01	73
en17	jeqcho	2021-02-19 09:54:14	3
en16	jeqcho	2021-02-19 09:53:34	4	Tiny change: 't problem C2)\n\n- [' -> 't problem 1486C2)\n\n- ['
en15	jeqcho	2021-02-19 09:53:10	7	Tiny change: '107906435]\n\n- [sub' -> '107906435] (367C)\n\n- [sub'
en14	jeqcho	2021-02-19 09:52:46	7	Tiny change: '107908687]\n\nIndeed' -> '107908687] (604B)\n\nIndeed'
en13	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	jeqcho	2021-02-19 09:46:20	22
en11	jeqcho	2021-02-19 09:43:39	1
en10	jeqcho	2021-02-19 09:42:50	80
en9	jeqcho	2021-02-19 09:33:43	30
en8	jeqcho	2021-02-19 09:31:45	94	Tiny change: ',a+n,-1)-a; // get i' -> ',a+n,-1)-a-1; // get i'
en7	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	jeqcho	2021-02-19 09:16:14	8	Tiny change: '`mid+1`, `lef+1` etc.\n\' -> '`mid+1`, `rig-1` etc.\n\'
en5	jeqcho	2021-02-19 08:24:52	258	Tiny change: '0, rig = n-1;\nwhile(l' -> '0, rig = n;\nwhile(l'
en4	jeqcho	2021-02-19 08:04:27	316	Tiny change: ' $\log N$.' -> ' $\log N$. Thanks to [user:marvenlee] for inspiring this blog.'
en3	jeqcho	2021-02-19 07:42:06	3
en2	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	jeqcho	2021-02-19 07:15:15	157	Initial revision (saved to drafts)

История