c++二分法查找_二分法查找python代码

c++二分法查找_二分法查找python代码二分法:二分法应用条件:1)数组为有序数组。2)同时题目还强调数组中无重复元素,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的。区间的定义:区间的定义不同代码就不同。1)定义target在[left,right]区间while(left<=right)要使用<=,因为left==right是有意义的,所以使用<=。if(nums[middle]>target)right要赋值为middle-1,因为当前这个nums[mid

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

二分法:

二分法应用条件:1)数组为有序数组。2)同时题目还强调数组中无重复元素,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的。

区间的定义:

区间的定义不同代码就不同。
1)定义target在[left, right]区间
while (left <= right) 要使用 <= ,因为left == right是有意义的,所以使用 <=。if (nums[middle] > target) right 要赋值为 middle – 1,因为当前这个nums[middle]一定不是target,那么接下来要查找的左区间结束下标位置就是 middle – 1。
以leecode704为例:

// 定义target在[left, right]区间
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;
    }
};

Jetbrains全家桶1年46,售后保障稳定

2)如果说定义 target 是在一个在左闭右开的区间里[left, right) :

// 定义target在[left, right)区间
// 版本二
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;
    }
};

参考:
代码随想录:https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E6%80%BB%E7%BB%93

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/230801.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号