目录
介绍
二分查找适用于已经排序的序列，通过对搜索区间折半的方式查找目标元素。
基本的二分搜索
基本的二分查找适用于在已经排序的无重复元素的序列中，查找一个目标值。。
思路
查找左边界的二分搜索，假设查找区间为 \([0, n)\) ，那么：
- 如果中间元素大于目标值，右指针移动到 \(mid - 1\) 位置;
- 如果中间元素小于目标值，左指针移动到 \(mid + 1\) 的位置；
- 如果中间元素等于目标值，则结束查找，返回结果；
注意：如果遍历完整个序列，都没有找到匹配的值，那说明序列中不包含目标值。
代码实现：
from typing import List
def binary_search(nums: List[int], target: int):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
if __name__ == "__main__":
print(binary_search([1, 2, 3, 4, 5, 6, 7, 8], 6))
查找左边界的二分搜索
如果已经排序的序列包含重复元素，即待查找的目标值target可能包含重复元素，就需要换一种方式查找。
例如，我们要从升序的序列\(nums = [1, 2, 3, 4, 5, 5, 5, 6, 6, 7, 8]\)，中查找第一个出现的元素\(5\)的序号，那么就要用到查找左边界的二分搜索方法。
思路
查找左边界的二分搜索，假设查找区间为 \([0, n)\) ，那么：
- 如果中间元素大于等于目标值，右指针移动到 \(mid\) 位置;
- 如果中间元素小于目标值，左指针移动到 \(mid + 1\) 的位置；
如果查找完所有的元素后，左指针针超出数组边界，或者，左指针指向的元素不等于目标值，则，原始数组中不存在目标值；否则，就返回左指针。
代码实现：
from typing import List
def binary_search_left(nums: List[int], target):
left, right = 0, len(nums)
while left < right:
mid = left + (right - right) // 2
if nums[mid] >= target:
right = mid
else:
left = mid + 1
if left >= len(nums) or nums[left] != target:
return -1
return left
if __name__ == "__main__":
print(binary_search_left([1, 2, 3, 4, 5, 5, 5, 7, 7, 7, 8], 5))
print(binary_search_left([1, 2, 3, 4, 5, 5, 5, 7, 7, 7, 8], 6))
查找右边界的二分搜索
同理，如果我们要从升序序列中查找出最后一次出现的元素，就要通过查找右边界的二分搜索方法。
思路
查找右边界的二分搜索，假设查找区间为 \([0, n)\) ，那么：
- 如果中间元素大于目标值，右指针移动到 \(mid\) 位置；
- 如果中间元素小于等于目标值，左指针移动到 \(mid + 1\) 的位置；
如果指针 \(left - 1\) 不在数组内，或者，指针 \(left - 1\) 指向的元素不等于目标值，那么原始数组不包含目标值，否则，就返回指针 \(left - 1\)。
代码实现：
from typing import List
def binary_search_right(nums: List[int], target):
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid
if left -1 <= 0 or nums[left - 1] != target:
return -1
return left - 1
if __name__ == "__main__":
print(binary_search_right([1, 2, 3, 4, 5, 5, 5, 6, 6, 7, 8], 5))
print(binary_search_right([1, 2, 4, 5, 5, 5, 6, 6, 7, 8], 3))