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