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