算法刷题营【Day1】:: 704.二分查找：二分法详谈与相关刷题-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法刷题营【Day1】:: 704.二分查找：二分法详谈与相关刷题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

本内容是笔者结合《代码随想录》总结所得，记录学习过程，分享知识！

目录：
1. 开篇例题：704. 二分查找
2. 题解参考（模板写法）

- - 2.1 方法一：左闭右闭写法
- - 2.2 方法二：左闭右开写法

3. 模板解释：左闭右闭

- - 3.1 区间划定
- - 3.2 left 、right 移动问题
- - 3.3 循环条件选择：<=

4. 模板解释：左闭右开

- - 4.1 区间划定
- - 4.2 left 、right 移动问题
- - 4.3 循环条件选择：<
5. 相关题集

1. 开篇例题：704. 二分查找

例题：点击直飞

算法刷题营【Day1】:: 704.二分查找：二分法详谈与相关刷题

2. 题解参考

2.1 方法一：左闭右闭写法

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 左闭右闭：left：指向首元素，right：指向尾元素；
        int left = 0, right = nums.size()-1;
        // 注意循环条件：<=
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] > target ) right = mid - 1;
            else if(nums[mid] < target) left = mid + 1;
            else return mid;
        }
        return -1;
    }
};

2.2 方法二：左闭右开写法

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 左闭右开：left：指向首元素，right：指向尾元素下一个位置；
        int left = 0, right = nums.size();
        // 注意循环条件：<
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] > target ) right = mid;
            else if(nums[mid] < target) left = mid + 1;
            else return mid;
        }
        return -1;
    }
};

3. 模板解释：左闭右闭

3.1 区间划定

左闭右闭：即说的是：left 与 right 的初始值【两个“指针的指向” 】
左闭右闭：left：指向首元素，right：指向尾元素；（如下图）

算法刷题营【Day1】:: 704.二分查找：二分法详谈与相关刷题

3.2 left 、right 移动问题

由于是：左闭右闭区间情形，那么 left 和 right 一定指向顺序表中的某个值！
显然：

right 的移动：若：nums[mid] > target，则说明 target 不在 [mid，right] 区间范围内，此时移动 right，移动方式：right = mid -1;

left 的移动：若：nums[mid] < target，则说明 target 不在 [left，mid] 区间范围内，此时移动 left ，移动方式：left = mid +1;

算法刷题营【Day1】:: 704.二分查找：二分法详谈与相关刷题

3.3 循环条件选择：<=

显然，如果：顺序表中只有一个元素：left == right【由区间选择所得】
若选择： < （非 <= ）则：不会进入循环！
无法得到：mid 进行搜索判断！
直接返回结果：-1（未找到！）

4. 模板解释：左闭右开

4.1 区间划定

左闭右开：即说的是：left 与 right 的初始值【两个“指针的指向” 】
左闭右开：left：指向首元素，right：指向尾元素下一个位置；（如下图）

算法刷题营【Day1】:: 704.二分查找：二分法详谈与相关刷题

4.2 left 、right 移动问题

由于是：左闭右开区间情形，那么 left 一定指向顺序表中的某个值！但 right 不会指向任意一个值！
显然：

right 的移动：若：nums[mid] > target，则说明 target 不在 [mid，right) 区间范围内，此时移动 right，移动方式：right = mid;
难点：mid 在比较过程中，理解右端点移动，mid 指向的若不是目标值，则区间缩减时，mid 已经不存在新区间中了！！！

left 的移动：若：nums[mid] < target，则说明 target 不在 [left，mid] 区间范围内，此时移动 left ，移动方式：left = mid +1;

算法刷题营【Day1】:: 704.二分查找：二分法详谈与相关刷题