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