§ 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.