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:

• Recent problem 1486C2 107949041

• 367C 107949113

• 604B 107949183

• 237C 107949260

Indeed, there are many other ways of implementing binary search, check out pllk's blog.

UPD Applied improvements thanks to sergei_popov