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.