摘要:
基础的二分查找算法无论是概念还是实现都比较简单（关于 二分查找基础实现文章 可点击此处查看），但二分查找存在相对复杂的变体问题，如数据组中存在重复数据时需要查找第一个或最后一个等于目标数据的情况等，而类似的变体问题也是二分查找的应用场景，也就是查找近似值。
二分查找的变体
基础的二分查找实现比较简单，简单的二分查找能够解决的问题应用其他查找算法也同样可以实现，执行效率也相差无几，但二分查找这种算法的存在是有自己的应用场景的。
之前讲述二分查找的例子中数据比较简单，需要解决的问题也不复杂，首先数据中没有重复数据，其次解决的问题只是在数据组中找到目标数据对应元素。如果改变条件，数据组中有重复数据，需要查找数据组中第一位或最后一位等于目标数据的情况，这样的问题该如何用二分查找解决？类似的，如果是查找数据组中第一位大于等于或最后一位小于等于目标数据的情况，应用二分查找又该如何解决？
解决问题的思路
上面几种二分查找变体问题都是类似的，我们可以先思考「重复数据情况下查找第一位等于目标数据」的问题。
基本思路还是二分查找的实现思路，不过因为有重复数据，当查找到目标数据时需要再做一番思考。虽然此时查找到了目标数据，但不一定是第一位等于目标数据的数组元素。此时有两种情况，一种是当前元素就是第一位等于目标数据的数组元素，那当前元素应当满足其是数组的首位元素（其前一位没有数据）或其前一位元素不等于目标数据；另一种是当前元素不满足上一种情况的条件，也就是说不是第一位等于目标数据的数组元素，那需要查找到的元素肯定在当前元素之前，需要对这部分数据再次进行二分查找。
代码实现
查找第一位等于目标数据的元素
public static int searchFirstEqual(int[] a, int target) {
if(a.length < 1) { return -1;}
int high = a.length - 1, low = 0;
while(low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > target) {
high = mid - 1;
} else if(a[mid] < target) {
low = mid + 1;
} else {
if(mid == 0 || a[mid - 1] != target) {
return mid;
}
high = mid - 1;
}
}
return -1;
}
查找最后一位等于目标数据的元素
这个问题的解决思路与「查找第一位等于目标数据的元素」问题类似，只是第一位换作了最后一位，需要将查找到的元素判断条件修改一下，当查找到元素等于目标数据时，当前元素要不就是数组最后一个元素，要不其下一个元素不等于目标数据，否则在需要查找的元素肯定在当前元素之后，需要对这部分数据继续使用二分查找。
public static int searchLatestEqual(int[] a, int target) {
if(a.length < 1) { return -1;}
int high = a.length - 1, low = 0;
while(low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > target) {
high = mid - 1;
} else if(a[mid] < target) {
low = mid + 1;
} else {
if(mid == a.length - 1 || a[mid + 1] != target) {
return mid;
}
low = mid + 1;
}
}
return -1;
}
查找第一位大于等于目标数据的元素
解决了前两个问题再来解决这个问题也就不难了，与「查找第一位等于目标数据的元素」问题相比，无非就是将等于换成了大于等于，修改相应的判断条件即可。
public static int searchFirstGte(int[] a, int target) {
if(a.length < 1) { return -1;}
int high = a.length - 1, low = 0;
while(low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] >= target) {
if(mid == 0 || a[mid - 1] < target) {
return mid;
}
high = mid - 1;
} else if(a[mid] < target) {
low = mid + 1;
}
}
return -1;
}
查找最后一位小于等于目标数据的元素
比较一下问题，就知道这个问题与「查找最后一位等于目标数据的元素」问题相似度高达 99.99%，只要将相应的判断条件修改一下即可。
public static int searchLatestLte(int[] a, int target) {
if(a.length < 1) { return -1;}
int high = a.length - 1, low = 0;
while(low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > target) {
high = mid - 1;
} else if(a[mid] <= target) {
if(mid == a.length - 1 || a[mid + 1] > target) {
return mid;
}
low = mid + 1;
}
}
return -1;
}
总结
二分查找虽然简单，但解决变体问题时还是需要思考一番，在变体问题的代码实现时，需要注意 确定返回数据的条件 及 low 和 high 的数据更新。
尽管还有其他出色的查找算法，但二分查找在近似数据查找的问题上非常适合，在实际中像「IP 归属地查找」等问题都符合近似查找，解决这些问题也是二分查找的用武之地。
文章中如有问题欢迎留言指正
本章节代码已经上传GitHub，可点击跳转查看代码详情。
数据结构与算法之美笔记系列将会做为我对王争老师此专栏的学习笔记，如想了解更多王争老师专栏的详情请到极客时间自行搜索。
网友评论