亲宝软件园·资讯

展开

C语言 二分查找 C语言详细讲解二分查找用法

清风自在 流水潺潺 人气:0
想了解C语言详细讲解二分查找用法的相关内容吗,清风自在流水潺潺在本文为您仔细讲解C语言二分查找的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:C语言二分查找,C语言二分查找算法,下面大家一起来学习吧。

【力扣题号】704.二分查找 力扣题目链接

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4 

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1     

提示:

注意读题,数组为有序数组,且数组中无重复元素,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的。

在二分查找的过程中,保持不变量,就是在 while 寻找中每一次边界的处理都要坚持根据区间的定义来操作,这就是循环不变量规则。

写二分法,区间的定义一般为两种,左闭右闭即 [left, right],或者左闭右开即 [left, right)。

第一种写法,我们定义 target 是在一个在左闭右闭的区间里,也就是[left, right] 。因为定义 target 在 [left, right] 区间,所以有如下两点:

while (left <= right) 要使用 <= ,因为left == right是有意义的,所以使用 <=

if (nums[middle] > target) ,right 要赋值为 middle - 1,因为当前这个 nums[middle] 一定不是 target ,那么接下来要查找的左区间结束下标位置就是 middle - 1

// 版本一
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里,[left, right]
        while (left <= right) { // 当left==right,区间[left, right]依然有效,所以用 <=
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间,所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间,所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值,直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

如果说定义 target 是在一个在左闭右开的区间里,也就是[left, right) ,那么二分法的边界处理方式则截然不同。

有如下两点:

while (left < right),这里使用 < ,因为 left == right 在区间 [left, right) 是没有意义的

if (nums[middle] > target) ,right 更新为 middle,因为当前 nums[middle] 不等于 target,去左区间继续寻找,而寻找区间是左闭右开区间,所以 right 更新为 middle,即:下一个查询区间不会去比较 nums[middle]

// 版本二
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size(); // 定义target在左闭右开的区间里,即:[left, right)
        while (left < right) { // 因为left == right的时候,在[left, right)是无效的空间,所以使用 <
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; // target 在左区间,在[left, middle)中
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间,在[middle + 1, right)中
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值,直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

通过以上两种方法,要注意它们不同的地方:

① right 的初始值不一样

② 左右区间的更新值的差别

参考:《代码随想录》

加载全部内容

相关教程
猜你喜欢
用户评论