二分查找（Binary Search），是一种效率较高的查找方法。在面试或算法竞赛中，查找相关的问题最优解通常就是二分查找。特别在现场面试中尤其重要，常用二分查找来考察面试者的编码能力和算法思维。
二分查找也称为折半查找。如果一个查找问题能够用一个条件消除一半的查找区域，那么就对目标在特定空间搜索，从而减少查找空间。 虽然二分查找思路比较直观，但大部分面试者通常在边界处理的时候考虑不全，从而出错。
有很多原因导致二分查找处理边界失败！例如，当目标位于数组第0个索引时，或位于第(n - 1)个索引时，程序进入死循环。
接下来，本问将对二分查找算法进行从零开始分析，总结出一套python实现二分查找的代码模板，并分析算法复杂度！
1. 算法模板下面的代码是二分查找的一种标准实现方式：
left = 0
right = size of array # 数组的大小
while (left + 1 < right)
mid = (left + right) / 2 # 中间mid下标
if (array[mid] == target) # 检查已找到
return mid
else if (array[mid] < target)
continue search in right side # 在 右边区间搜索
else
continue search in left side # 在 左边区间搜索
if (array[left] == target) # 循环退出后进行判断
return left
return -1
复制代码逐一分析下上面伪代码：
-
第1行：
0作为左边left索引。 -
第2行：数组大小作为右边
right索引。因此，当访问right索引，需要小心越界。 -
第4行：当
left和right之间没有元素时，while循环结束。因此，注意如果数组中仅有一个元素，将跳过这个循环，此时需要14行代码进行处理。 -
第14行: 在循环外检查
left索引上的元素，因为循环退出时，它可能是需要查找的数字target。
下面是完整的二分查找代码：
def binarySearch(nums, target):
if len(nums) == 0:
return -1
# 左索引的初始值为 0
left = 0
# 右索引的初始值是数组中元素的数量
right = len(nums)
# left + 1 >= right 时将完成while循环
while left + 1 < right:
mid = (right + left) // 2;
if nums[mid] == target:
# mid是目标的索引
return mid
elif nums[mid] < target:
# 在数组的左半部分搜索没有意义
left = mid
else:
# 在数组的右半部分搜索没有意义
right = mid
# left 可以是目标的索引
if nums[left] == target:
return left
# 目标不存在于数组中
return -1
def main():
nums = [1,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59];
print("Index of 37 is ---> " + str(binarySearch(nums, 37)))
print("Index of 1 is ---> " + str(binarySearch(nums, 1)))
print("Index of 59 is ---> " + str(binarySearch(nums, 59)))
print("Index of 25 is ---> " + str(binarySearch(nums, 25)))
main()
复制代码以查找37为例进行动画演示：
现在，考虑算法能否正确处理边界情况：
- 目标是为数组中的第一个元素：
- 目标是数组中的最后一个元素：
- 目标不存在于数组中：
虽然二分查找问题都会因为考虑具体情况而陷入困境。但是，大多数二分查找问题都依赖于相同的核心概念。如果使用相同的处理思路，就可以轻松地绕过所有的具体问题。
本问中的二分查找算法建立在以下核心关键点：
-
left指向索引0。 -
rigth为数组大小(注意不是数组的最后一个元素索引)。 -
循环条件
left + 1 > right。 -
将
left或right移到中点mid索引。 -
在循环外的
left索引上检查是否匹配。
二分查找的基本特点是每次将搜索区域减少到是原始空间的一半。
假设当前搜索空间中有n个元素，每一次迭代，都会减少(n/2)个元素。搜索区域不断减半，从n到(n/2)，到(n/4)，到(n/8)，以此类推，直到区域大小变成1（除非在之前某个步骤中找到目标，直接退出）。
最后，要么找到目标值，要么证明它不存在于搜索空间中。那么总运行时间就是能走多少步（每次用n除以2），直到n变成1。 下面是算法在最坏情况下的直观表现：
- 当目标是数组第一个元素时：
- 当目标是数组最后一个元素时：
上面例子中数组有171717个元素。为了找到目标值，必须不断减半才能得到一个元素的情况，总迭代次数就是对数函数log2 17=4log_2\space 17=4log2 17=4。因此，最多444次迭代就足以使数组减少到一个元素。如果nnn代表总数，在经过log2 nlog_2 \space nlog2 n的次折半后就能找到答案，时间复杂度相当于O(log2 n)O(log_2 \space n)O(log2 n).
空间复杂度二分查找占用空间非常小，核心就是几个变量如left、right、mid，因此其空间复杂度为O(1)。
本文详细介绍了二分查找原理及其编码实现，结合大量动画演示，希望对你有所帮助。但二分查找的算法思维应用非常广，在面试中或leetcode上有大量二分变形的问题，如求波峰、波谷，旋转数组之类的。
python超全资料库安装包学习路线项目源码免费分享
