C/C++编程刷题分享—二分法查找

✅作者简介：嵌入式领域新星创作者，博客专家
✨个人主页：咸鱼弟
🔥系列专栏：剑指offer专栏

目录

1.题目描述

2.解题思路

2.1.提取题目信息     

2.2.知识点——二分法

3.参考代码

4.复杂度分析

---

1.题目描述

2.解题思路

2.1.提取题目信息     

• 给定一个元素升序的、无重复数字的整型数组 nums 和一个目标值 target
• 找到目标值的下标
• 如果找不到返回-1

2.2.知识点——二分法

分治即“分而治之”，“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题，子问题继续按照这样划分，直到问题可以被轻易解决；“治”指的是将子问题单独进行处理。经过分治后的子问题，需要将解进行合并才能得到原问题的解，因此整个分治过程经常用递归来实现。

思路：

本来我们可以遍历数组直接查找，每次检查当前元素是不是要找的值。

for(int i = 0; i < nums.length; i++)
{
    if(nums[i] == target)
        return i;
}

但是这样这个有序的数组我们就没有完全利用起来。我们想想，若是目标值比较小，肯定在前半区间，若是目标值比较大，肯定在后半区间，怎么评价大小？我们可以用中点值作为一个标杆，将整个数组分为两个区间，目标值与中点值比较就能知道它会在哪个区间，这就是分治的思维。

具体做法：

• step 1：从数组首尾开始，每次取中点值。
• step 2：如果中间值等于目标即找到了，可返回下标，如果中点值大于目标，说明中点以后的都大于目标，因此目标在中点左半区间，如果中点值小于目标，则相反。
• step 3：根据比较进入对应的区间，直到区间左右端相遇，意味着没有找到。

图示：

3.参考代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0;
        int r = nums.size() - 1;
        //从数组首尾开始，直到二者相遇
        while(l <= r){ 
            //每次检查中点的值
            int m = (l + r) / 2; 
            if(nums[m] == target)
                return m;
            //进入左的区间
            if(nums[m] > target) 
                r = m - 1;
            //进入右区间
            else 
                l = m + 1;
        }
        //未找到
        return -1; 
    }
};

4.复杂度分析

• 时间复杂度：O(log2n)O(log_2n)O(log2​n)，对长度为nnn的数组进行二分，最坏情况就是取2的对数
• 空间复杂度：O(1)O(1)O(1)，常数级变量，无额外辅助空间

二分法查找是一种基本的查找方法，需要大家掌握其实现原理。