共计 2035 个字符，预计需要花费 6 分钟才能阅读完成。
1. 概述
前面说到了二分查找问题，看起来非常的简单，的确，前面的两种实现都不难，代码也很容易写，因为那只是最基础的二分查找问题了。今天来看看几种稍微复杂的二分查找问题：
查找第一个等于给定值的元素
查找最后一个等于给定值的元素
查找第一个大于等于给定值的元素
查找最后一个小于等于给定值的元素
1. 查找第一个等于给定值的元素
假如有一个数组 data[1,3,5,5,5,7,8,10,12]，我们要查找第一个等于 5 的值，该怎么实现呢？如果按照普通的二分查找算法，取中间 data[4]=5，刚好等于要查找的值 5，所以程序就返回下标 4。但是很明显不正确，因为我们要找的是第一个 5，下标为 2，那应该怎么实现呢？先来看看代码吧：
public static int findFirst(int[] data, int value) {
int low = 0;
int high = data.length – 1;
while (low <= high) {
int mid = low + ((high – low) >> 1);
if (data[mid] == value) {
if (mid == 0 || data[mid – 1] != value) return mid;
else high = mid – 1;
}
else if (data[mid] < value) low = mid + 1;
else high = mid – 1;
}
return -1;
}
这里的代码和前面的普通二分查找很类似，只是在判断 data[mid] == value 的时候，会有一些不一样，如果 mid 等于 0，则表示这是数组的第一个元素，那么肯定就是我们要找的元素，第二种情况，如果 mid 的前一位不等于 value，那么也是我们要找的元素。
3. 查找最后一个等于给定值的元素
这种变形的二分查找和上面的这种情况很类似，还是利用上面的那个数组 data[1,3,4,5,5,5,5,10,12]，我们要查找最后一个等于 5 的元素。实现的代码也和上面的类似：
public static int findLast(int[] data, int value) {
int low = 0;
int high = data.length – 1;
while (low <= high) {
int mid = low + ((high – low));
if (data[mid] == value) {
if (mid == data.length – 1 || data[mid + 1] != value) return mid;
else low = mid + 1;
}
else if (data[mid] < value) low = mid + 1;
else high = mid – 1;
}
return -1;
}
在 data[mid] == value 的时候，会进行判断，如果 mid 等于数组 length – 1，则说明是数组的最后一个元素，那么肯定是我们查找的，如果 mid 的前面一个元素不等于 value，则说明也是我们要查找的。逻辑跟上面说到的查找第一个等于给定值的情况相反。
4. 查找第一个大于等于给定值的元素
例如一个数组 data[1,3,5,5,5,8,8,8,10,12]，我们要查找第一个大于等于 7 的值，就是下标为 5 的值 8，应该怎么做呢？实际上实现的思路和上面的两种问题类似，代码其实还更简洁：
public static int findFirstBigger(int[] data, int value) {
int low = 0;
int high = data.length – 1;
while (low <= high){
int mid = low + ((high – low) >> 1);
if (data[mid] >= value){
if (mid == 0 || data[mid – 1] < value) return mid;
else high = mid – 1;
}
else low = mid + 1;
}
return -1;
}
当 data[mid] >= value 的时候，进行统一处理，这里有两个判断，一是如果 mid 等于 0，表示 mid 是数组的第一个元素，那么肯定就是我们要找的元素，第二种情况是，如果 mid 的前一个元素小于 value，那么也是我们要查找的元素。
5. 查找最后一个小于等于给定值的元素
有了对前面三种情况的理解，其实再来写这种情况的代码就很简单了，直接给出代码：
public static int findLastSmaller(int[] data, int value) {
int low = 0;
int high = data.length – 1;
while (low <= high){
int mid = low + ((high – low) >> 1);
if (data[mid] <= value){
if (mid == data.length – 1 || data[mid + 1] > value) return mid;
else low = mid + 1;
}
else high = mid – 1;
}
return -1;
}
当然，这只是众多二分查找变形问题中常见的几种，可以多理解一下，自己动手实现一下。也可以拓展一些思维，例如上面的查找小于等于或者大于等于的情况，如果只是查找小于或者大于，该怎么实现呢，只需要将代码的一些细节稍作修改即可。
