§ 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);
  }
}