二分查找中区间（左闭右闭、左闭右开、左开右闭）的理解 C++实现

学习来源：代码随想录 (programmercarl.com)

在写二分查找算法中，什么情况应该定义while(left<=right),什么情况应该定义while(left

还有更新左右边界时候 ，什么情况下需要 +1什么情况下需要-1等等。这些是我在学习二分查找算法的时候遇到的问题不知大家是否有同样的问题。下面是我在代码随想录上面学习的理解。写成博客帮助有需要的朋友，初学者，轻喷。

在二分查找算法中，如何确定目标值的区间？一般来说有三种，即[left.right] [left.right) (left.right] 

在整个算法过程中我们要遵循 循环不变量原则，即每次更新区间时都要跟一开始定义的区间一致。

下面代码摘自 代码随想录，对注释做了简明化修改，帮助理解

第一种区间类型：左闭右闭，[left.right] 

// [left.right] 
class Solution {
public:int search(vector& nums, int target){// 定义target在左闭右闭的区间里，[left, right]int left = 0;int right = nums.size() - 1; // 当left==right，区间[left, right]依然有效，所以用 <=while (left <= right){ // 防止溢出 等同于(left + right)/2。两个int类型变量相加可能超出int的最大范围int middle = left + ((right - left) / 2);if (nums[middle] > target) {// target 在左区间，-1理由：nums[middle] > target可知target不等于nums[middle]，不必再包含该值，但要保证更新区间后还是左闭右闭，所以[left, middle - 1]right = middle - 1; } else if (nums[middle] < target) {// target 在右区间，+1理由同上left = middle + 1; }else{ // nums[middle] == target 即 数组中找到目标值，直接返回下标return middle; }}// 未找到目标值return -1;}
};

第二种区间类型：左闭右开。[left.right) 

//[left, right)
class Solution {
public:int search(vector& nums, int target) {// 定义target在左闭右开的区间里，即：[left, right)int left = 0;int right = nums.size(); // 因为left == right的时候，在[left, right)是无效的空间，所以使用 > 1);if (nums[middle] > target) {// target 在左区间，= middle理由：nums[middle] > target可知target不等于nums[middle]，不必再包含该值，但要保证更新区间后还是左闭右开，所以[left, middle）right = middle; } else if (nums[middle] < target) {// target 在右区间，middle + 1理由：nums[middle] > target可知target不等于nums[middle]，不必再包含该值，但要保证更新区间后还是左闭右开，所以[middle + 1, right）left = middle + 1; } else { // nums[middle] == target 即 数组中找到目标值，直接返回下标return middle; }}// 未找到目标值return -1;}
};

第三种不常用，类似第二种类型。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！