Leetcode704

二分查找

​ 力扣二分查找题目

​ 二分查找这个算法简单，但却会屡屡出错，问题就出在边界上。针对边界的问题，有两种写法，一种是闭区间，一种是开区间。
​ 此外，需注意的是，使用二分查找的条件：已排序的数组，无重复元素。

第一种写法

• 搜索区间：[left , right];
• left、right初始化：left = 0; right = array.size -1;（也就说最右边数组元素的下标，例长度为7的数组，最右边数组下标为6）;
• 终止条件：left <= right;
• left改变：left = middle + 1;
• right；right = middle-1；
• middle = left + ((right - left) / 2);（防止溢出 等同于(left + right)/2）;

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;
    }

第二种写法

• 搜索区间；[left, right);
• left、right初始化：left = 0; right = array.size ;（数组的长度，例长度为7的数组，以该索引访问数组则会越界，故上面的搜素区间为左开右闭）。
• 终止条件：left < right;
• left改变：left = middle + 1;
• right；right = middle；
• middle = left + ((right - left) / 2);（防止溢出 等同于(left + right)/2）;

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;
    }

类似题目

搜索插入位置
在排序数组中查找元素的第一个和最后一个位置

参考

代码随想录