当前位置：首页 > news >正文

【优选算法】Binary-Blade：二分查找的算法刃（上）

news 来源：原创 2025/7/17 19:19:17

文章目录

1.概念解析
2.二分查找的简单模版
3.二分查找的进阶模版
4.x的平方根
5.搜索插入位置
希望读者们多多三连支持
小编会继续更新
你们的鼓励就是我前进的动力！

本篇是优选算法之二分查找算法，该算法是一种高效的在有序数组中查找特定元素的搜索算法

1.概念解析

🚩什么是二分查找算法？

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

2.二分查找的简单模版

✏️题目描述：

在这里插入图片描述

✏️示例：

在这里插入图片描述

传送门：二分查找

题解:

在一个无论是有序还是无序的数列里，一般最先想到的就是暴力解法遍历一遍，然后符合条件则成立，这种方法固然是好用，但是一般在搜索数据的过程中，数据量庞大，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次，明显效率高了不止一点

💻代码实现：

#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;}
};

3.二分查找的进阶模版

✏️题目描述：

在这里插入图片描述

✏️示例：

在这里插入图片描述

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

题解:

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

💻第一步：

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

在这里插入图片描述

先找左端点，主要的思路还是一样，找出二段性，那么为什么是像如图分类呢？我们要找的是左端点等于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就会一直不动死循环

💻代码实现：

#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 };}
};

4.x的平方根

✏️题目描述：

在这里插入图片描述

✏️示例：

在这里插入图片描述

传送门：x的平方根

题解:
💻细节问题：

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

在这里插入图片描述

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

💻代码实现：

#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;}
};

5.搜索插入位置

✏️题目描述：

在这里插入图片描述

✏️示例：

在这里插入图片描述

传送门：搜索插入位置

题解:
💻细节问题：

在这里插入图片描述

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

💻代码实现：

#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新年快乐！

希望读者们多多三连支持

小编会继续更新

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

请添加图片描述

文章目录

1.概念解析

2.二分查找的简单模版

3.二分查找的进阶模版

4.x的平方根

5.搜索插入位置

希望读者们多多三连支持

小编会继续更新

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

相关文章：