五月集训-09【二分查找】

• 前言
• 一、练习题目
• 二、思路及题解
• • 1. LC35-搜索插入位置
  • 2. LC704-二分查找
  • 3. 剑指 Offer 53 - I. 在排序数组中查找数字 I
  • 4. LC911-在线选举
• 总结

        欢迎大家积极在评论区留言一起讨论交流，知无不言，言无不尽，共同进步。本文是 二分查找 专题，更多其他专题内容详见《LeetCode每月集训系列》

方法一：

（1）设插入的位置为 pos，它成立的条件为：nums[pos − 1] < target ≤ nums[pos]；
（2）如果存在这个目标值，返回的索引同样也是 pos，因此可以将两个条件合并得出：在一个有序数组中找第一个大于等于 target 的下标；
（3）然后直接套用二分查找法即可。

代码如下：

class Solution {
public:
    int searchInsert(vector& nums, int target) {
        int n = nums.size();
        int left = 0, right = n - 1, ans = n;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (target <= nums[mid]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
};

方法一：

（1）常规二分查找，此处使用了闭区间模版。

代码如下：

class Solution {
public:
    int search(vector& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;  // 注意 -> 搜索闭区间[left, right]

        while(left <= right) {  // 当left==right，区间[left, right]依然有效
            int mid = left + (right - left) / 2;  // 防止溢出 <- (left + right) / 2
            if(nums[mid] > target) {
                right = mid - 1;  // target 在左区间，所以[left, middle - 1]
            } else if(nums[mid] < target) {
                left = mid + 1;  // target 在右区间，所以[middle + 1, right]
            } else {  // nums[mid] == target
                return mid;  //找到目标值，返回下标
            }
        }
        return -1;  //未找到目标值，返回 -1
    }
};

方法一：

（1）binarySearch函数旨在查找目标数字 target 在数组 nums 中的 插入点 ，且若数组中存在值相同的元素，则插入到这些元素的右边。
（2）通过将目标数字的右边界与比目标小1元素的右边界（即目标元素的左边界）做差后的值即为目标元素的个数。

代码如下：

class Solution {
public:
    int binarySearch(vector& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    int search(vector& nums, int target) {
        int leftIdx = binarySearch(nums, target - 1);
        int rightIdx = binarySearch(nums, target);
        return rightIdx - leftIdx;
        }
        
};

方法一：

（1）看不懂题，以后再补。

代码如下：

/

        题目难不要怕，只要每个月的每一天都坚持刷题学习，总有一天会熟练掌握的。欢迎加入【知识星球｜英雄算法联盟】与我们一同早起刷刷刷⛽️