## § Correctness of binary search

#### § Closed-closed intervals

```
int binsearch(int l, int r, int val, int *xs) {
while(l <= r) {
int mid = (l+r)/2;
if (xs[mid] == val) {
return mid;
} else if (xs[mid] < val) {
l = mid+1;
} else {
r = mid -1;
}
return -1;
}
```

#### § Closed-open / half-open intervals

```
int binsearch(int l, int r, int val, int *xs) {
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`

.