【二分查找】——模板

二分查找模板题

一、题目要求

给定一个长度为n的非递减数组和一个数字target，要求找到数组中第一个大于等于target的位置pos，数组下标从 0 开始。如果不存在大于等于target的数字，则输出 -1。

二、输入格式

1. 第一行：为两个正整数n和target，其中1≤n,target≤10^5。分别表示数组长度和要查询的数字。
2. 第二行：为n个正整数a1,a2,...,an，其中1≤ai≤10^5，表示给定的非递减数组。

三、输出格式

输出数组中第一个大于等于target的位置pos，如果不存在，则输出 -1。

四、示例

1. 输入：
   • 7 5
   • 2 3 5 6 7 8 9
2. 输出：
   • 2

暴力解法

一个一个试

二分查找

二分查找代码思路的通俗解释：

一、整体目标

我们的目标是在一个非递减（升序）的整数数组中找到第一个大于等于给定目标值target的元素的位置。如果不存在这样的元素，则返回 -1。

二、初始化

1. 首先，我们有一个整数数组nums，它的长度为n。我们设置两个指针，left指向数组的第一个元素的位置，初始值为 0；right指向数组的最后一个元素的位置，初始值为n - 1。
   • 这就好比我们在一个有很多房间的长廊里找东西，一开始left站在第一个房间门口，right站在最后一个房间门口，确定了我们的搜索范围是整个长廊。

三、循环查找

1. 进入一个循环，只要left小于right，就一直循环下去。
   • 这个循环就像是我们在不断缩小搜索范围，直到找到目标或者确定目标不存在。
2. 在循环中，计算中间位置mid，计算公式是mid = left + (right - left) // 2。
   • 这就相当于我们每次都把长廊分成两部分，然后去中间的那个房间看看。
3. 如果中间位置的元素nums[mid]小于目标值target，说明目标值如果存在的话，一定在mid的右边。所以我们把left更新为mid + 1，这样就缩小了搜索范围到右边的部分。
   • 就像我们确定目标不在左边这一半长廊了，于是left走到了原来中间那个房间的右边一个房间，继续搜索右边的长廊。
4. 如果中间位置的元素nums[mid]大于等于目标值target，说明目标值如果存在的话，一定在mid的左边或者就是mid本身。所以我们把right更新为mid，这样就缩小了搜索范围到左边的部分。
   • 这时候我们觉得目标可能在左边这一半长廊，于是right走到了原来中间那个房间，继续搜索左边的长廊。

四、确定结果

1. 当循环结束时，也就是left和right相等或者left大于right了。这时候我们检查left位置的元素是否大于等于目标值。
   • 如果是，说明我们找到了第一个大于等于目标值的位置，就是left。
   • 如果不是，说明数组中不存在大于等于目标值的元素，就返回 -1。

n, target = map(int, input().split())
nums = list(map(int, input().split()))left, right = 0, n - 1
while left < right:mid = left + (right - left) // 2if nums[mid] < target:left = mid + 1else:right = mid
if nums[left] >= target:print(left)
else:print(-1)

二分查找适用于以下几种情况：

1. 有序数据查找元素：数据是有序排列的，要查找特定元素，能高效定位，时间复杂度为$O(logn)$，比线性查找的$O(n)$快很多。
2. 查找边界值：在单调变化（递增或递减）的数据中，找满足某个条件的边界值，比如满足某个不等式的最小或最大数值。
3. 动态规划优化：在动态规划问题里，用于优化状态转移过程，快速查找满足条件的区间内元素。
4. 广范围数据搜索：数据分布范围广，二分查找可以缩小搜索区间，快速定位目标或目标区间，避免大量无效搜索。