概念解析s

🚩什么是二分查找算法？

每次比较中间元素，通过判断中间元素与目标元素的大小关系，将搜索区间缩小一半，持续这个过程，直至找到目标元素或者确定目标元素不存在

二分查找的简单模版

✏️题目描述：

在这里插入图片描述

✏️示例：

在这里插入图片描述

传送门：二分查找

题解:

在一个无论是有序还是无序的数列里，一般最先想到的就是暴力解法遍历一遍，然后符合条件则成立，这种方法固然是好用，但是一般在搜索数据的过程中，数据量庞大，O(n)的时间复杂度还是太大了，那么这时候就要使用时间复杂度为O(log n)的二分查找

💻第一步：

二分查找说的就是折中查找，那么二段性就是重要的第一步，找出左右区间不同的地方

在这里插入图片描述

比如这题就是 target 的左区间小于它，右区间大于它，根据这个特性不断调整left和right的位置，接下来看一下具体实现

💻第二步：

不断循环算出mid的值，与target作比较，如果大于target，说明mid所指位置及后面的数都不是符合target的数，right = mid - 1；如果小于target，说明mid所指位置及前面的数都不是符合target的数， left = mid + 1

在这里插入图片描述

💻细节问题：

🚩循环条件

循环条件为 left<=right ，因为当 left 变得比 right 大时，查找区间自然就不存在了；如果只是 left < right，会遗漏掉最后一个元素。例如，在数组只有一个元素时，初始left = 0，right = 0， 若条件是 left < right，循环压根不会进入，直接判定未找到，但实际上这个唯一元素还没检查，使用 left <= right 就能保证这种单元素数组也能被正确查找

在这里插入图片描述

🚩时间复杂度

不断将区间折中，最终折中为区间长度为1即找到指定元素，即 n / $2^x$ = 1，解得 x = $\log_n$

在这里插入图片描述

假设要查找2³²个数中的一个数，暴力解法就是有多少数就找多少次，而二分查找是指数关系，只需要找32次，明显效率高了不止一点

💻代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <vector>
using namespace std;

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;
            if (nums[mid] > target)
            {
                right = mid - 1;
            }
            else if (nums[mid] < target)
            {
                left = mid + 1;
            }
            else
            {
                return mid;
            }
        }
        return -1;
    }
};

二分查找的进阶模版

✏️题目描述：

在这里插入图片描述

✏️示例：

在这里插入图片描述

传送门：二分查找的进阶模版

题解:

题目中的非递减的意思就是数据要么递增要么不变

💻第一步：

如果用简单的二分查找方法必然是不行的，因为不知道找到的数是否为端点值，因此在此基础上衍生出查找左右端点的进阶二分查找

在这里插入图片描述

先找左端点，主要的思路还是一样，找出二段性，那么为什么是像如图分类呢？我们要找的是左端点等于target的情况，那么应该在左端点和前一个数之间划分，那么在右区间寻找的时候就会有等于target

请添加图片描述

在左区间寻找，mid所指位置及前面的数都不是符合target的数，即使指向左端点前一个数，也是要越过该数，指向左端点，即left = mid + 1；在右区间寻找，mid所指的位置可能是左端点值，所以不能越过左端点，即right = mid

💻第二步：

接着寻找右端点也是同理

在这里插入图片描述

我们要找的是右端点等于target的情况，那么应该在右端点和后一个数之间划分，那么在左区间寻找的时候就会有等于target

在这里插入图片描述

在右区间寻找，mid所指位置及后面的数都不是符合target的数，即使指向右端点后一个数，也是要越过该数，指向右端点，即right = mid - 1；在左区间寻找，mid所指的位置可能是右端点值，所以不能越过右端点，即left = mid

💻细节问题：

🚩循环条件

在这里插入图片描述

无论是找左端点还是右端点，有right = mid和left = mid，通过举例会发现，当left和right汇合到一个数时，因为这两种情况会一直停在那儿不动，会死循环

🚩求mid操作

请添加图片描述

求mid的公式是否加1其实是对偶数个数字的简单模版时候是没区别的，无非是先求右边还是先求左边的区别。但是在如图进阶二分模版极端条件下，求左端点，只有两个数时，如果用加1的公式的话，mid会指向右边，由于right = mid，right就会一直不动死循环

请添加图片描述

右端点也是同理，在如图进阶二分模版极端条件下，求右端点，只有两个数时，如果用不加1的公式的话，mid会指向左边，由于left = mid，right就会一直不动死循环

💻代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <vector>
using namespace std;

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

x的平方根

✏️题目描述：

在这里插入图片描述

✏️示例：

在这里插入图片描述

传送门：x的平方根

题解:
💻细节问题：

学习完模版后二分基本上都很简单，一般都是用进阶模版，确定二段性很重要

在这里插入图片描述

由于求平方根是向下取整，所以把等于的情况划分到左区间

💻代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
using namespace std;

class Solution 
{
public:
    int mySqrt(int x) 
    {
        if (x < 1)
        {
            return 0;
        }
        long long left = 0, right = x;
        while (left < right)
        {
            long long mid = left + (right - left + 1) / 2;
            if (mid * mid <= x)
            {
                left = mid;
            }
            else
            {
                right = mid - 1;
            }
        }
        return left;
    }
};

搜索插入位置

✏️题目描述：

在这里插入图片描述

✏️示例：

在这里插入图片描述

传送门：搜索插入位置

题解:
💻细节问题：

在这里插入图片描述

由于是在target大一位的数插入，所以把等于的情况划分到右区间

💻代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <vector>
using namespace std;

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

🌸 愿新年如初春的花开般灿烂，芬芳四溢，盈满心间；
✨ 告别2024年的些许遗憾，迎接2025年的满怀希望；
🌟 愿你在新的一年里，心怀星光，步履坚定；
🎉 愿每一份努力都有收获，每一个梦想都能成真；
❤️ 愿日子如诗，岁月如歌，温柔且浪漫；
🌿 每一步都走得从容，每一天都活得明媚；
🎀 愿你在新岁中，遇见更闪亮的自己；
2025，期待你的美好与光芒！
各位2025新年快乐！

希望读者们多多三连支持

小编会继续更新

你们的鼓励就是我前进的动力！

请添加图片描述