Reduction of search space in binary search

Question

I am solving the classical binary search problem:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty()) return -1;

        int lo=0, hi=nums.size()-1;
        while(lo<hi) {
            int mid=lo+(hi-lo)/2;
            //if element found at position mid, return mid
            if(nums[mid]==target) return mid;
            if(nums[mid]<target) lo=mid+1;
            //why not hi=mid-1, since if mid _could_ have our answer, we would 
            //have already returned above
            else hi=mid;
        }
        
        // if element not found, return -1;
        return nums[lo]==target ? lo : -1;
    }
};

I am seeking an intuitive explanation for setting hi=mid (specifically with the while loop condition as lo<hi and not lo<=hi). I think we should set it as hi=mid-1, since we know that mid cannot contain our answer (if it did, then we would have already returned). Yes, I can try it out on a few examples, but I am trying to intuitively understand how the search space reduces while developing the logic (before getting to coding) so that I can come up with a concrete algo that can work on all examples.

Answer 1

I am seeking an intuitive explanation for setting hi=mid (specifically with the while loop condition as lo<hi and not lo<=hi). I think we should set it as hi=mid-1, since we know that mid cannot contain our answer (if it did, then we would have already returned).

There are two main potential issues here:

1. Correctness. Does the function terminate, returning the correct answer, for all inputs?

   • with hi=mid, yes. For this, we can observe that when the loop condition lo<hi holds, mid is always strictly less than hi but not less than lo, therefore setting mid=hi reduces the search interval. We can also observe that when that alternative is exercised, the target value must be in the reduced interval if it is present at all. Since the search space is finite and is reduced at every iteration, the computation must eventually reach an interval size of 1 (and therefore terminate) if it does not find the target sooner.

   • with hi=mid-1, also yes. The argument is the same, but it is worth noting that it can be the case that mid == lo, which yields the possibility that hi would be set less than lo. That does not present a practical problem as the function is written, but it is a bit untidy.

2. Efficiency. Could the function arrive at the correct result in fewer steps?

   Using hi=mid-1 does not make the function asymptotically faster. It is O(log n) either way. Moreover, on any given problem, the two alternatives will test different sequences of values, so either alternative might happen to complete in fewer cycles than the other when the target value is present. Intuition suggests that shrinking the search interval that little bit more would be a slight win on average, especially in the case where the target value is not present, but that gain is proportionally insignificant except for in the cycles where the interval is already pretty small.

I am trying to intuitively understand how the search space reduces while developing the logic (before getting to coding) so that I can come up with a concrete algo that can work on all examples.

Either alternative works, and there is no reason to expect a noticeable speed difference. It comes down, then, to style and personal sensibility. Myself, I prefer hi=mid in this case so as to avoid ever producing a situation where hi < lo. Others might prefer hi=mid-1 for symmetry.

---

Side note: one cannot, on the other hand, change from lo=mid+1 to lo=mid. Because it is possible for mid=lo+(hi-lo)/2 to result in mid==lo, one needs the lo=mid+1 alternative to ensure that the interval shrinks on every cycle.