二分查找（Binary Search）是在有序数组中查找某一特定元素的搜索算法。主要的算法流程如下：
- 从数组的中间元素开始搜索，如果中间元素即是需要查找的元素，即搜索过程结束。
- 如果中间元素比要搜索的元素大，那么要搜索的元素就在中间元素的左侧（升序数组，否则在右侧），对左侧有序子数组进行相同的取中间元素再比较的过程；如果中间元素比要搜索的元素小，就对右侧子数组进行同样的操作。
- 结束条件（递归出口）：如果子数组为空。
值得注意的是加减 1 缺少了，在做这种较简单的算法时可以画出图来：
Python 实现时可以分用不用左右边界坐标的方式，如利用递归的方式如下：
def search(self, nums: List[int], target: int) -> int:
if not nums:
return -1
left, right = 0, len(nums)-1
return self.binary_search(nums, left, right, target)
def binary_search(self, nums: List[int], left: int, right: int, target: int) -> int:
if left > right:
return -1
mid = (left + right) >> 1
if nums[mid] == target:
return mid
elif nums[mid] > target:
right = mid - 1
else:
left = mid + 1
return self.binary_search(nums, left, right, target)
迭代的方式如下：
def binarySearch(arr, l, r, x):
while l <= r:
mid = l + (r - l)/2;
# Check if x is present at mid
if arr[mid] == x:
return mid
# If x is greater, ignore left half
elif arr[mid] < x:
l = mid + 1
# If x is smaller, ignore right half
else:
r = mid - 1
# If we reach here, then the element
# was not present
return -1
二分搜索常见考察点
- 对于边界条件的考察以及代码实现的能力
- 常见题目题目的变化
- 给定处理或查找对象的不同，有无重复
- 判断条件不同
- 要求返回的要求不同
- 在有序循环数组中进行二分搜索
注意：
mid = (left+right) / 2 # 加和太大的话可能溢出
mid = left + (right-left) / 2
LeetCode 题型总结
- 查找有无重复，有重复找到重复的
- 查找最小值