二分查找的第三个变形版本:在给定排序序列中查找第一个大于等于给定值的元素。
有了昨天的基础,来解决今天这个问题,是不是很简单?所不同的是判断节点不一样了,我们之前的需求都是查找等于给定值,现在变成了大于等于给定值,所以我们要在 nums[mid] >= num 这个判断条件上做文章,思路还是和之前两个变形版本类似,当 mid 已经是最左边的元素,或者 mid 的前一个元素值小于给定查询值,则 mid 对应元素即为满足条件的元素,否则继续往前查找。对应的 C++ 实现代码如下:
#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]) {
if (mid == 0 || nums[mid - 1] < num){
return mid;
} else {
return binary_search_internal(nums, num, low, mid - 1);
}
} else if (num > nums[mid]) {
return binary_search_internal(nums, num, mid + 1, high);
}
}
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;
}
同样,与之相对的,还有我们这次分享中最后要讨论的一个二分查找的变形版本:在给定序列中查找最后一个小于等于给定值的元素。
有了前面几个变形版本的铺垫,相信你自己就可以写出对应的实现代码了。这次的判断节点变成了 nums[mid] <= num,其中 num 是待查找的元素值,当 mid 已经是最后一个元素索引,或者 mid 的后一个元素值大于 num 则当前 mid 对应元素就是要查找的元素,否则要继续往后查找。
对应的 C++ 实现代码如下:
#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]) {
if (mid == sizeof(nums) - 1 || nums[mid + 1] > num){
return mid;
} else {
return binary_search_internal(nums, num, mid + 1, high);
}
} else if (num < nums[mid]) {
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;
}
评论区