§ Correctness of binary search

§ Closed-closed intervals

// search index i in interval [l, r] for value `val`.
// returns i such that xs[i] = val.
// return -1 otherwise.
int binsearch(int l, int r, int val, int *xs) {
  while(l <= r) {
  int mid = (l+r)/2;
  // l <= mid < r
  if (xs[mid] == val) {
    return mid;
  } else if (xs[mid] < val) {
    // go to higher range, this is too small.
    // have already considered mid.
    // l <= mid => l < mid+1
    l = mid+1; // [l, r] -> [mid+1, r]
  } else {
    // go to lower range, this is too larger.
    // have already considered mid, so go to mid-1.
    // mid < r => mid-1 < r
    // [l, r] -> [l, mid-1]
    r = mid -1;
  }
  return -1;
}

§ Closed-open / half-open intervals

// search in interval [l, r) for value `val`
int binsearch(int l, int r, int val, int *xs) {
  // [l, l+1) = { l }
  if (r == l + 1) { return l; }
  int mid = (l+r)/2;
  if (xs[mid] <= val) {
    return binsearch(l, mid, val, xs);
  } else {
    return binsearch(mid, r, val, xs);
  }
}

• We have (l <= mid < r) since floor division of the form (l+r)/2 will pull values "downward".
• Furthermore, if r = l + 1 we end the recursion.
• Thus, we are guaranteed that we will have that r >= l + 2.
• Hence, mid = (l+r)/2 will be larger than l as r >= l + 1. We see this from the algebra m = (l + r) >= (l + l + 2)/2 >= l + 1.
• So we have l < l+1 <= mid < r. This establishes a "gap" l < mid < r, which is possible since all the smallest non-trivial interval [l, r) we consider will be [l, l+1, l+2) (recall that r=l+1 is the base case).
• Thus, we have that: l is to the left of mid=l+1 is to the left of r>=l+2.
• So, the intervals [l, mid) and [mid, r) will be smaller, as we cleanly "separate" out l, mid, and r.