二分查找在算法题目中是十分常见的一类题目，但这类题目往往要求二分查找找出解集中的第一个、最后一个解，这个时候通常的二分查找算法就无法直接套用了。
本文将列举 5 种二分查找的变体应用，它们分别是：
- Contains，是否包含目标
- Index of first occurrence of a key，目标第一次出现的下标
- Index of last occurrence of a key，目标最后一次出现的下标
- Index of least element greater than (or equal) to key，最小的大于（或大于等于）目标的下标
- Index of greatest element less than (or equal to) key，最大的小于（或小于等于）目标的下标
之后会更新几篇文章针对不同类型的题目进行分析。
这 5 中变体算法的代码如下：
class BinarySearch {
/**
* 是否包含 key
*
* @param nums 输入数组
* @param key 目标
* @return true 包含；false 不包含
*/
public static boolean contains(int[] nums, int key) {
int low = 0, high = nums.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2; // (low + high) / 2 可能导致溢出，因此采用这种方式计算
int midVal = nums[mid];
if (midVal == key) {
return true;
}
if (midVal < key) {
low = mid + 1;
} else if (midVal > key) {
high = mid - 1;
}
}
return false;
}
/**
* @param nums 输入数组
* @param key 目标
* @return 返回 key 第一次出现时的下标
*/
public static int first(int[] nums, int key) {
int ans = -1, low = 0, high = nums.length - 1;
while (low <= high) {
int mid = low + (high - low + 1) / 2;
int midVal = nums[mid];
if (midVal < key) {
// key 在 mid 右边
low = mid + 1;
} else if (midVal > key) {
// key 在 mid 左边
high = mid - 1;
} else if (midVal == key) {
// mid 左边可能存在 key，因此左移右边界
ans = mid;
high = mid - 1;
}
}
return ans;
}
/**
* @param nums 输入数组
* @param key 目标
* @return 返回 key 最后出现时的下标
*/
public static int last(int[] nums, int key) {
int ans = -1, low = 0, high = nums.length - 1;
while (low <= high) {
int mid = low + (high - low + 1) / 2;
int midVal = nums[mid];
if (midVal < key) {
// key 在 mid 右边
low = mid + 1;
} else if (midVal > key) {
// key 在 mid 左边
high = mid - 1;
} else if (midVal == key) {
// 右边界任然可能存在 key，因此将 low 右移
ans = mid;
low = mid + 1;
}
}
return ans;
}
/**
* @param nums 输入数组
* @param key 目标
* @return 最小大于 key 的元素的下标
*/
public static int leastGreater(int[] nums, int key) {
int ans = -1, low = 0, high = nums.length - 1;
while (low <= high) {
int mid = low + (high - low + 1) / 2;
int midVal = nums[mid];
if (midVal < key) {
// 最小大于 key 的元素在 mid 右边
low = mid + 1;
} else if (midVal > key) {
// 任然存在比 midVal 更小的解，因此将 high 左移
ans = mid;
high = mid - 1;
} else if (midVal == key) {
// 最小大于 key 的元素在 mid 右边
// 可以和 midVal < key 的情况进行合并
low = mid + 1;
}
}
return ans;
}
/**
* @param nums 输入数组
* @param key 目标
* @return 最大的小于 key 的元素的下标
*/
public static int greatestLesser(int[] nums, int key) {
int ans = -1, low = 0, high = nums.length - 1;
while (low <= high) {
int mid = low + (high - low + 1) / 2;
int midVal = nums[mid];
if (midVal < key) {
// 可能存在比 midVal 更大的解，因此右移 low
ans = mid;
low = mid + 1;
} else if (midVal > key) {
// midVal 过大，解在 mid 左边
high = mid - 1;
} else if (midVal == key) {
// 同样，可以和 midVal > key 进行合并
high = mid - 1;
}
}
return ans;
}
}
其中算法 leastGreater 和 greatestLesser 只需稍作修改即可用于求解大于等于以及小于等于的情况，因此不做赘述。
其中，变体 2 （目标第一次出现时的下标，上面的 first 算法）和 C++ std::lower_bound() 很类似：
template<class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value)
{
ForwardIt it;
typename std::iterator_traits<ForwardIt>::difference_type count, step;
count = std::distance(first, last);
while (count > 0)
{
it = first;
step = count / 2;
std::advance(it, step);
if (*it < value)
{
first = ++it;
count -= step + 1;
}
else
count = step;
}
return first;
}
变体 4，最大的小于（或小于等于）目标的元素的下标（上面的 greatestLesser 算法）和 C++ 的 std::upper_bound() 算法很类似：
template<class ForwardIt, class T>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value)
{
ForwardIt it;
typename std::iterator_traits<ForwardIt>::difference_type count, step;
count = std::distance(first, last);
while (count > 0)
{
it = first;
step = count / 2;
std::advance(it, step);
if (!(value < *it))
{
first = ++it;
count -= step + 1;
}
else
count = step;
}
return first;
}