本文参考:
分享丨【题单】二分算法（二分答案/最小化最大值/最大化最小值/第K小） - 力扣（LeetCode）
本文主要详细讲解基础的二分算法中的查找，包括原理和模板，并用leetcode和洛谷的一些例题来进行实际题目讲解，如果觉得有帮助或者写的不错可以点个赞
目录
二分查找算法介绍
什么是二分查找？
我觉得洛谷那个例子举的很好
在一本英语词典中翻找一个单词的时候，可以从前往后一面一面的翻找，这就是顺序查找
但是英语词典里面的单词是按照字典序排的，那么可以先翻到词典的页数中间位置，然后根据要查找的单词再从前或者往后翻
这种思想就是二分查找
注意，二分查找一般只适用于有序的数组
那二分查找步骤是什么呢？
基本步骤如下:
- 确定初始范围：将搜索范围设置，比如整个数组。
- 计算中间位置：找到当前搜索范围的中间位置。
- 比较与缩小范围：
- 如果中间位置的值是目标值，返回该位置。
- 如果目标值小于中间位置的值，缩小范围到左半部分。
- 如果目标值大于中间位置的值，缩小范围到右半部分。
- 重复步骤2和3，直到找到目标值，或者搜索范围为空（未找到目标值）
- 核心思想：每次迭代将搜索范围缩小一半
二分查找的代码怎么写呢？
代码编写思路：
根据二分查找的步骤，我们可以得出实际代码的大致的编写方法:
初始化：
- 定义两个指针，
left和right迭代搜索：
- 在
left小于等于right的情况下，重复以下步骤：
- 计算中间位置
mid：mid- 比较目标值
target与arr[mid]的大小：
- 如果
target等于arr[mid]，则找到了目标值- 如果
target小于arr[mid]，则目标值在左半部分，更新right- 如果
target大于arr[mid]，则目标值在右半部分，更新left结束条件：
- 如果在迭代过程中找到了目标值，返回目标值所在的位置。
- 如果
left超过right而没有找到目标值，说明目标值不在数组中，返回 -1 表示未找到
刚学习的可以根据上面的步骤尝试写一遍
根据上面步骤，我们可以写出以下代码(Python)（有详细注释）:
闭区间写法:
def binary_search(arr: List[int], target: int) -> int:
'''
在有序数组中查找目标值的索引。
如果目标值存在，返回其索引；否则返回 -1。
参数：
arr (List[int]): 一个有序的整数数组。
target (int): 需要查找的目标值。
返回值：
int: 目标值的索引，如果不存在则返回 -1。
'''
# 初始化搜索范围的左右边界
left, right = 0, len(arr) - 1
# 当左边界不超过右边界时，继续搜索
while left <= right:
# 计算中间位置
mid = left + (right - left) // 2
# 如果中间值等于目标值，返回中间位置
if arr[mid] == target:
return mid
# 如果中间值小于目标值，说明目标值在右半部分，调整左边界
elif arr[mid] < target:
left = mid + 1
# 如果中间值大于目标值，说明目标值在左半部分，调整右边界
else:
right = mid - 1
# 如果循环结束后仍未找到目标值，返回 -1
return -1需要注意一点，在python中整数是”无限范围的“，可以比较无脑，可以直接写“mid = （right + left）// 2”但是其他语言中，整数相加可能会存在溢出的情况，也就是常说的”爆int“, 所以在计算中间位置的时候，建议这么编写：
mid = left + (right - left) // 2，先减后加
上述代码是闭区间写法，对于这种写法，为什么运行条件是left <= right? 为什么更新边界的时候是变成mid + 1或mid - 1？
现在用实际例子来进行理解这种写法的边界问题：
比如arr = [1, 3, 5, 7, 9, 11, 13, 15, 16],target = 7
开始的时候：l = 0, r = 8,那么mid = l + (r - l) // 2 = 4
此时arr[mid] = 9 > target = 7
缩小r = mid - 1 = 3
l = 0, r = 3
那么mid = l + (r - l) // 2 = 1
此时arr[mid] = 3 < target = 7
增大l = mid + 1 = 2
l = 2, r = 3
那么mid = l + (r - l) // 2 = 2
此时arr[mid] = 5 < target = 7
增大l = mid + 1 = 3
l = 3, r = 3
那么mid = 3,arr[mid] = target 返回mid
通过实际例子模拟可以看到，可能会存在left == right 的情况，循环条件就得这么写left <= right
其他写法:
左闭右开写法:
#左闭右开写法
def binary_search(arr: List[int], target: int) -> int:
left, right = 0, len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid
return -1开区间写法:
#开区间写法
def binary_search(arr: List[int], target: int) -> int:
left, right = -1, len(nums)
while left + 1 < right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid
else:
right = mid
return -1这两种写法我就不举例子了，可以自己对着例子模拟一遍就可以理解了，写题目的时候用一种自己习惯的就行
库函数用法：
Python:
bisect_left(a, x, lo=0, hi=len(a))：在有序序列a中查找元素x应该插入的位置，并返回插入位置的索引。如果有多个相同元素，插入在其左侧。
bisect_right(a, x, lo=0, hi=len(a))：在有序序列a中查找元素x应该插入的位置，并返回插入位置的索引。如果有多个相同元素，插入在其右侧。
lo：指定搜索的起始位置。默认值为0，即从序列的开始处开始搜索。hi：指定搜索的结束位置（不包含）。默认值为序列的长度len(a)，即搜索到序列的末尾。
C++:
lower_bound(first, last, val)函数在有序范围[first, last)中查找第一个不小于val的元素的迭代器。upper_bound(first, last, val)函数在有序范围[first, last)中查找第一个大于val的元素的迭代器。- 这两个函数都返回一个迭代器,指向满足条件的元素。如果没有找到满足条件的元素,它们会返回
last迭代器- 题目一般求解的是下标，则可以用数组开始的迭代器
nums.begin()进行减法运算，迭代器之间的减法运算会得到两个迭代器之间的距离,即元素的索引位置。
关于二分查找算法时间复杂度的简单证明:
在二分查找中，每次比较都会将搜索范围减半，这使得算法的时间复杂度是对数级别的。具体来说，假设有 n 个元素，每次比较都将搜索范围减半，即 n -> n/2 -> n/4 -> ... -> 1。在最坏情况下，需要进行 k 次比较才能找到目标元素或确定其不存在，其中 k 为满足 2^k <= n 的最大整数。因此，可以得出 k = log₂n。
综上所述，由于每次比较都将搜索范围减半，最多进行 log₂n 次比较就可以找到目标元素或确定其不存在。因此，二分查找的时间复杂度是 O(log n)。
例题一：
题目链接:
题目大意解析和思路:
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5 输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2 输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7 输出: 4
题目的意思可以理解成在数组中找出第一个大于或等于target元素的下标，比如示例1
当target大于数组最大值的时候，返回数组长度即可，比如示例3
题目又要求时间复杂度是O(logn)那么就是二分算法，那具体怎么做呢
仔细理解二分查找模板代码
当left <= right的时候，查找的区间不断缩小，当left > right的时候，退出循环
此时left的下标对于的值刚好是大于或者等于target的元素
正好是这题所求的条件，那么可以直接写代码了
代码(Python):
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left代码(C++):
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 - 1;
}
}
return left;
}
};库函数写法(Python):
根据上面我写的库函数
bisect_left(a, x, lo=0, hi=len(a))：在有序序列a中查找元素x应该插入的位置，并返回插入位置的索引。如果有多个相同元素，插入在其左侧。
这题可以直接使用这个，由于力扣中已经导入相关的类了，那可以直接写
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
return bisect_left(nums, target)库函数写法(C++):
同理，参考我刚刚写的库函数
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
return ranges::lower_bound(nums.begin(), nums.end(), target) - nums.begin();
}
};例题二：
P2249 【深基13.例1】查找 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目大意解析和思路:
输入 n 个不超过 10^9 的单调不减的（就是后面的数字不小于前面的数字）非负整数 a1,a2,…,an，然后进行 m 次询问。对于每次询问，给出一个整数 q，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 −1 。
输入格式
第一行 2 个整数 n 和 m，表示数字个数和询问次数。
第二行 n 个整数，表示这些待查询的数字。
第三行 m 个整数，表示询问这些数字的编号，从 1 开始编号。
输出格式
输出一行，mm 个整数，以空格隔开，表示答案。
输入输出样例
输入
11 3 1 3 3 3 5 7 9 11 13 15 15 1 3 6
输出
1 2 -1
题目的意思就是找出下面一行每个数字在上面数组中的位置，从1开始编号（这个好恶心）
这个数据量用循序查找肯定是不行的，所以需要用二分
这个里面会出现相同的数字，需要输出数字在序列中第一次出现的编号，我的思路是：
在二分查找的过程中，找到a[mid] == target的时候
由于是找最小的那个位置，此时可以先让res = mid
然后缩小r = mid - 1,再在[l , r]这个区间内找是否有a[mid] == target的情况
最后的答案即为最小的位置
代码(C++):
(最近看jiangly大佬的代码是写std::的，我这样的习惯还是挺好的，试试这样写)
long long binary_search(std::vector<long long>& a, int target) {
int l = 0, r = a.size() - 1, res = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (a[mid] == target) {
res = mid;
r = mid - 1;
} else if (a[mid] < target) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return res;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int m, n;
std::cin >> n >> m;
std::vector<long long> a1(n);
std::vector<int> a2(m);
for (int i = 0; i < n; i++) {
std::cin >> a1[i];
}
for (int i = 0; i < m; i++) {
std::cin >> a2[i];
}
std::vector<int> res(m);
for (int i = 0; i < m; i++) {
res[i] = binary_search(a1,a2[i]);
if (res[i] != -1) {
res[i]++;
}
}
for (int i = 0; i < m; i++) {
std::cout << res[i] << " ";
}
std::cout << "\n";
return 0;
}我之后也会陆续更新一些比较高质量的基础算法详细解释，和一些解算法题的小技巧
如果感兴趣，可以看看我之前写的文章:
不定长滑动窗口算法详细解释(带例题的详细解法)-CSDN博客
算法题练习小技巧之区间合并--套路详细讲解带例题和源码(Python,C++)-CSDN博客
标签：二分,target,int,mid,查找,例题,left From： https://blog.csdn.net/2401_83669813/article/details/140957613