二分查找的常用模板

二分查找算法是一种高效率的查找算法，尤其适用于数组或者有序列表这种数据结构。本文将会从以下几个角度介绍二分查找的常用模板。

一、算法思路

二分查找算法，也称折半查找，是一种基于比较目标值和中间元素的教科书式算法。每次查找排除掉一半的区间，直到查找到目标值或者区间为空为止。

首先，我们需要先确定数组的左、右两个指针。然后通过循环或递归的方式，依次比较中间元素和目标元素的大小。如果目标元素小于数组中间元素，则在数组左半部分继续搜索，否则在数组右半部分继续搜索。通过不断迭代缩小搜索区间，即可在数组中找到目标元素或确定目标元素不存在于数组中。

二、算法模板

下面是一份二分查找算法的常用模板：

```python

def binarySearch(nums: List[int], target: int) -> int:

left, right = 0, len(nums) - 1

while left <= right:

mid = (left + right) // 2

if nums[mid] == target:

return mid

elif nums[mid] < target:

left = mid + 1

else:

right = mid - 1

return -1

```

三、时间复杂度

二分查找算法的时间复杂度为O(logn)，其中n为数组的长度。由于每次迭代会将搜索区间缩小一半，因此时间复杂度是对数级别的增长。

四、适用场景

二分查找算法的主要适用场景是有序数组或者有序列表。例如，在电话簿或者字典中查找目标单词，就可以利用二分查找算法来提高查找效率。

此外，二分查找算法还可以应用在一些数学问题上，如求解函数的零点或者最值等。

五、算法优化

在实际应用中，二分查找算法可以针对不同情况进行优化：

1. 左右指针初始化

在一些情况下，左右指针的初始值影响二分查找的效率。例如，当目标元素可能出现在右边界的情况下，可以将右指针初始化为数组长度减一。

2. 选择中间值方式

一般情况下，中间值的计算方式可以使用 left + (right - left) / 2，这种方式可以保证计算的结果不会溢出。

3. 双指针缩小搜索范围

在一些情况下，可以利用双指针来迅速缩小搜索范围。例如，在旋转数组中查找最小值的问题中，可以通过比较中间值和右边界的元素大小，来缩小搜索区间。