如何用Python实现二分查找？

二分查找其实老简单了，代码是三行五行能写完，但要用得不出bug还得说说。

你想啊，就像你去超市找某个货架上的某样东西，明知道货架是从小到大排的，你是不是每次都往中间看一眼？发现目标比中间那个小，你就去左边半边再找，比中间大就往右边。每次都能排除一半，效率嘎嘎高，跟翻字典查单词一个套路。

这个思路丢到代码里其实就几步：

1. 先找头和尾
2. 循环，别傻愣着
3. 每次算一下中间那个数，看是不是目标
4. 不是就缩小范围，继续来

我那会儿写过最直白的一个，代码你直接抄没问题，反正网上一大把（不过咱讲点自己的小心得哈）：

defbinary_search(nums, target):
    left = 0
    right = len(nums) - 1
while left <= right:
        mid = (left + right) // 2
# print("当前中间下标：", mid)  # 调试的时候真好用
if nums[mid] == target:
return mid
elif nums[mid] < target:
            left = mid + 1
else:
            right = mid - 1
return-1

你别看代码短哈，这里面的left <= right可别乱写成<啥的，否则有时候就漏掉边界那个。以前有次我就踩坑，找半天目标不在，结果明明就在头或者尾。

还有一次，早上赶工改个bug，写二分查找，突然有人喊我去搬快递，回来一看代码里mid = (left + right) // 2，万一那数组特别大，left + right溢出了咋办？其实现在python不容易溢出，但C++那种就有坑。所以保险起见有的人会这样写：

mid = left + (right - left) // 2

这样绝对不溢出，也显得你专业。反正写python你俩怎么都行，心里有数就好。

找不到返回啥？

对了，还有个经常被问的点，就是没找到目标，返回啥？通常都是-1，有的面试官还喜欢问返回下标还是返回False？一般按惯例就返回-1，实用。

你要是非得要递归写法，能不能？当然能——不过递归写多了容易脑袋大，尤其一早上没睡醒的时候：

defbinary_search_recursion(nums, target, left, right):
if left > right:
return-1
    mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
return binary_search_recursion(nums, target, mid + 1, right)
else:
return binary_search_recursion(nums, target, left, mid - 1)

用的时候记得最开始别写错：

idx = binary_search_recursion([1,3,5,7,9], 7, 0, 4)

我印象最深的是有次面试前一晚，自己练手，发现死活找不到数组里第一个等于目标的那个，原来写漏了边界判断。那晚搞得太困，后来早上醒来直接把循环条件和下标判等那块仔细理了一遍，才发现少考虑了一种情况。所以说别迷信背代码，关键还是理解你到底缩小哪一段了，怎么不丢数据。

哦对，群里前两天小李还说：“东哥你二分查找都能讲成鸡汤，服了。”其实技术这玩意，生活里就是一堆细节，别看就是几行代码，写顺了就美滋滋，写错了能让你找一天bug。

反正就是这么回事，二分查找用在排序数组里真香，其他啥链表、乱序啥的别想了，别硬套。