【优选算法必刷100题】第017题（二分查找算法）：二分查找

艾莉丝努力练剑

发布于 2025-11-16 20:35:06

1230

文章被收录于专栏：C / C++C / C++

二分查找算法简介：

017 二分查找

力扣链接：704. 二分查找

力扣题解链接：朴素二分查找模版解决【二分查找】问题

题目描述：

1.1 算法思路——二分查找

无序数组具有二段性也可以用二分查找。这里是有序的。

当我们发现一个规律，并且根据这个规律选取此某一个点后，能把这个数组分成两部分，根据规律能够多有选择性地舍去一部分，进而在另一个部分里面继续查找的时候，此时就可以用二分查找算法。

1.2 算法流程

1、定义left，right指针，分别指向数组的左右区间。

2、找到待查找区间的中间点mid，找到之后分三种情况讨论：

（1）arr[mid]== target说明正好找到，返回mid的值；（2）arr[mid]>target说明[mid，right]这段区间都是大于target的，因此舍去右边区间，在左边[left，mid - 1]的区间继续查找，即让right = mid - 1，然后重复2过程；（3）arr[mid]くtarget说明[left，mid]这段区间的值都是小于target的，因此舍去左边区间，在右边[mid+1，right]区间继续查找，即让left=mid+ 1，然后重复2过程。

3、当left与right错开时，说明整个区间都没有这个数，返回1。

1.3 算法实现

1.3.1 选择1 / 2划分点

//选取 1/2 点
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;//标记左右端点
        while (left <= right) {
            int mid = left + (right - left) / 2;// 防止溢出
            // int mid = (right + left) / 2;// C++ && Java这里直接加会有溢出的风险，会不准
            if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
            else return mid;
        }
            return -1;
    }
};

时间复杂度：O(logn)，空间复杂度：O(1)。

1.3.2 选择1 / 3划分点

// 选取 1/3 点
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;//标记左右端点
        while (left <= right) {
            int mid = left + (right - left) / 3;// 防止溢出，右移1/3
            // int mid = (right + left) / 3;// C++ && Java这里直接加会有溢出的风险，会不准
            if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
            else return mid;
        }
            return -1;
    }
};

时间复杂度：O(logn)，空间复杂度：O(1)。

1.3.3 选择1 / 4划分点

// 选择 1/4 划分点
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;//标记左右端点
        while (left <= right) {
            int mid = left + (right - left) / 4;// 防止溢出
            // int mid = (right + left) / 4;// C++ && Java这里直接加会有溢出的风险，会不准
            if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
            else return mid;
        }
            return -1;
    }
};

时间复杂度：O(logn)，空间复杂度：O(1)。

1.3.4 其他划分点

……

1.3.5 总结

在力扣这个平台似乎并不能很明显的感受到1 / 2是时间复杂度最优秀的划分点。

虽然力扣看不出来，但是我们要知道：1 / 2是最优划分这个结论背后是有严格的数学推理的——概率学中的求数学期望，求数学期望的证明过程太长了，这里就不演示了。

1.4 朴素二分模版

二分查找的三大模板——

下面我们就来学习一下三大模板之一的【朴素二分模版】。

这里博主说两种写法等价、朴素模版中+1还是不+1都无所谓，我们可以来验证一下——

// +1
//选取 1/2 点
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;//标记左右端点
        while (left <= right) {
            int mid = left + (right - left) / 2;// 防止溢出
            // int mid = (right + left) / 2;// C++ && Java这里直接加会有溢出的风险，会不准
            if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
            else return mid;
        }
            return -1;
    }
};