There are only two correct ways to implement binary search. Here is the less known one.

```
int binary_search(int *nums, int len, int target) {
int l = -1;
int r = len;
while (l < r - 1) {
int mid = (l + r) >> 1;
if (nums[mid] < target) {
l = mid;
} else {
r = mid;
}
}
return r;
}
```

This version returns the index of the first element in `nums`

that is greater than or equal to the target. If there is no such element, `len`

will be returned.

Although only `r`

is returned, `l`

could also be of interest. It contains the index of the last element that is smaller than the target. if there is no such element, `l`

will be `-1`

, which is a good indicator for "no such element". It is always the case that `r = l + 1`

when the algorithm terminates.

Replace `<`

with `<=`

, `l`

will be the last element that is **smaller than or equal to** the target, and `r`

will be the first element that is **greater than** the target, subject to the same special cases above if there is no such element. If operator `<=`

is not implemented, use `!(target < nums[mid])`

which is logically equivalent to `nums[mid] <= target`

.

Note if there is only one element in `nums`

that is equal to target, `(<,r)`

and `(<=,l)`

will converge. If target is not in `nums`

, see the following picture.

Or if you prefer precise definitions:

op | symbol | is the | that is | or |
---|---|---|---|---|

< | l | last | smaller than (<) |
-1 |

<= | l | last | smaller than or equal to (<=) |
-1 |

< | r | first | greater than or equal to | len |

<= | r | first | greater than | len |

The third line in the above table `(<, r)`

implements `lower_bound`

, while the fourth line `(<=, r)`

implements `upper_bound`

.

The drawback of this approach, is that the initially `l`

is set to a special value `-1`

. This might not always be possible if the index is of type `usize`

. The advantage, is that neither `l`

or `r`

need to plus or minus one in each iteration, which leaves no room for error.

## The other way

The other correct way of implementing binary search, is the approach used in `lower_bound`

and `upper_bound`

in C++ STL. It can be found on cppreference.com.

The interesting aspect of this implementation is that the two pointers started as a valid range `[0, len)`

, but terminated as an empty range `[r, r)`

, when `l`

and `r`

are equal. To me that makes the implementation harder to reason about. I acknowledge that you don't have to reason about it very often, though.

## Criteria of being correct

To be correct, `binary_search`

must return a reasonable value in all of the following cases, when looking for `2`

.

```
1 2 3
1 2
1 3
2 3
1
2
3
1 1 2 2 3 3
1 1 2 2
1 1 3 3
2 2 3 3
1 1
2 2
3 3
```

You might also want to duplicate each case into a odd length one and an even length one.