Binary Search algorithm implementations

Question

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

Option1: low = 1, high = arr.length

2. Condition for loop

Option1: while(low < high)

Option2: while(low <= 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

EDIT: Assumptions taken are 3 state output. Array indices start at 0.

Answer 1

Well, you can make it work in lots of ways, but:

1) I use low=0, high=arr.length. If I'm going to call variables low and high, then I want low<=high always, even at the end of the search. This is also easier to think about when arr.length==0

2) while (low<high). This corresponds to the answer for (1). When the loop is done, I like low==high, so I don't have to worry about which one to use.

3) Always use mid=low+(high-low)/2 or mid = low+((high-low)>>1). The other option overflows when the array gets too long and gives negative results.

4) This depends on what kind of comparison you're using (3-state vs. 2-state output), in addition to the other answers. For 2-state compares and the above-answers, you get low=mid+1 or high=mid. This is ideal, since it's obvious that the range gets smaller every iteration -- mid+1 > low obviously, and mid < high, because low<high (that's the loop condition) and (high-low)/2 rounds downward.