The variations of binary search , how to find the suitable one?

General Questions
#1

I have come across multiple problems which use variations of binary search to reach the final answer. These problems include finding floor of square root of number, checking if number is a perfect square or not, finding minimum in rotated array, finding first index of number in array etc.

All algorithms contain a low, high and mid variable which are appropriately modified.

I read several variations of these algorithms online and there are always high chances of by one error in these algorithms, causing it to miss the corner cases. For the following variations, is there any standard which can help me understand which one should be used when?

1. Initialisation of variables

Option1: low = 0, high = arr.length

Option2: low = 0, high = arr.length - 1

Option3: low = 1, high = arr.length

2. Condition for loop

Option1: while(low < high)

Option2: while(low <= high)

Option3: while(low+1 <= high)

3. Mid variable calculation

Option1: mid = (low + high) / 2;

Option2: mid = low + (high - low) / 2;

4. Condition Checking and updates to low and high

Option1: low = mid AND high = mid

Option2: low = mid AND high = mid - 1

Option3: low = mid + 1 AND high = mid

Option4: low = mid + 1 AND high = mid - 1

#2

1 / 2 / 4: any of these could work

3: option 1 behaves differently depending on the sign of low + high. option 2 doesn’t, though you should make sure that high - low doesn’t overflow. (as noted in the Binary Search module)

#3

i watched the codeforces EDU on binary search and the instructor seems to allows vary variable initialization and while coditions and he justifies it , so it seems that it depends on the problem , isn’t it?

#4

Of course, you will need to vary the initialization. Other than that, the rest should be essentially the same for any problem involving binary search over integers. If you check my template, you can see that I typically use one of the following two functions.

tcTU> T fstTrue(T lo, T hi, U f) {
	++hi; assert(lo <= hi); // assuming f is increasing
	while (lo < hi) { // find first index such that f is true 
		T mid = lo+(hi-lo)/2;
		f(mid) ? hi = mid : lo = mid+1; 
	} 
	return lo;
}
tcTU> T lstTrue(T lo, T hi, U f) {
	--lo; assert(lo <= hi); // assuming f is decreasing
	while (lo < hi) { // find last index such that f is true 
		T mid = lo+(hi-lo+1)/2;
		f(mid) ? lo = mid : hi = mid-1;
	} 
	return lo;
}