二分查找
1. 基础知识
算法简介
二分查找是在有序数组中寻找某一元素的查找算法，它的主要思想就是将搜索空间缩小为原来的一半。尽管二分查找的思想非常简单，但是很多人也容易出错，主要问题出现在代码对边界值的处理、比较符号带不带等号这些细节上。
算法流程
- 设数组
arr = [0, 1, …, N]，初始化左边界left=0，右边界right=len(arr)-1，mid为左右指针的中点； - 取出
mid指向的元素，如果此元素为查找的元素，结束查找过程，并返回结果； - 如果
mid指向的元素大于查找目标，因为数组有序，因此接下来查找arr[left, mid-1]；如果此元素小于查找目标，那么接下来查找arr[mid+1, right]； - 更新
left、right和mid，不断重复此过程，如果搜索空间为空，说明数组arr中不存在所要寻找的值。
复杂度分析
- 平均时间复杂度 $O(\log N)$
- 最坏时间复杂度 $O(\log N)$
- 空间复杂度
- 迭代实现： $O(1)$
- 递归实现： $O(\log N)$