符合标准的二分查找条件的序列一般是比较理想的情况,如果要查找的元素在序列中有多个怎么办?所以我们要给大家介绍的第一个常见的变形版本,就是在一个给定排序序列中查找第一个等于给定值的元素。在继续往下看之前,你不妨借机先思考一下要怎么实现。
其实关键节点就在于在序列中找到值等于待查找元素值时的处理。如果此时 mid 位置已经到了序列的最左边,不能再往左了,或者序列中索引小于 mid 的上一个元素值不等于待查找元素值,那么此时 mid 就是第一个等于待查找元素值的位置;否则还要继续往前找。
对应的 C++ 实现代码如下,其他地方都一样,就是 num == nums[mid] 时的处理逻辑变了:
#include <iostream>
int binary_search_internal(int* nums, int num, int low, int high){
if (low > high){
return -1;
}
int mid = (low + high) / 2;
if (num < nums[mid]) {
return binary_search_internal(nums, num, low, mid - 1);
} else if (num > nums[mid]) {
return binary_search_internal(nums, num, mid + 1, high);
} else {
if (mid == 0 || nums[mid - 1] != num) {
return mid;
} else {
return binary_search_internal(nums, num, low, mid - 1);
}
}
}
int binary_search(int* nums, int num) {
return binary_search_internal(nums,num,0, sizeof(nums) - 1);
}
int main() {
int nums[] = {1,2,3,4,5,6};
std::cout << binary_search(nums, 3) << std::endl;
return 0;
}
既然有第一个等于给定值的查询,自然就有最后一个等于给定值的查询,这就是二分查找的第二个变形版本:在给定已排序序列中查找最后一个等于给定值的元素。实现逻辑和上面类似,只需要改动 num == nums[mid] 时的处理逻辑,只是这时的条件变成了 mid 位置到了序列的最右边,不能再往后了,或者索引大于 mid 的后一个元素值不等于带查找元素,才返回 mid,否则,还要继续往后找。在我给出实现代码之前,你能自行实现这段代码吗?不防动手写一下,或者头脑中构思下。
下面我来给出查找最后一个等于给定值的元素的 C++ 实现代码,由于其他部分都一样,我只给出 binary_search_internal 函数的代码:
int binary_search_internal(int* nums, int num, int low, int high){
if (low > high){
return -1;
}
int mid = (low + high) / 2;
if (num < nums[mid]) {
return binary_search_internal(nums, num, low, mid - 1);
} else if (num > nums[mid]) {
return binary_search_internal(nums, num, mid + 1, high);
} else {
if (mid == sizeof(nums) - 1 || nums[mid + 1] != num) {
return mid;
} else {
return binary_search_internal(nums, num, low, mid - 1);
}
}
}
评论区