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.net/blog/entry/9901).↵
↵
**UPD** Applied improvements thanks to [user:sergei_popov,2021-02-19]
↵
#### 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;↵
}↵
}↵
~~~~~↵
↵
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 =
int ans =
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.
↵
~~~~~↵
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
↵
- 367C [submission: 10
↵
- 604B [submission:1079
↵
- 237C [submission:1079
↵
Indeed, there are many other ways of implementing binary search, check out [pllk's blog](https://codeforces.net/blog/entry/9901).↵
↵
**UPD** Applied improvements thanks to [user:sergei_popov,2021-02-19]