二分查找（binary search）是一个有名的算法，它是分治思想的应用。但你真的理解了二分查找吗？

教材中常常用这个问题引入二分查找：

输入一个有序数组

A，在其中寻找

target，如果存在则输出它在数组中的下标，否则输出

-1

这个例子太经典了，以至于“有序数组”在同学脑海里印象过于深刻，可以形成条件反射，看到某些题目中数组有序，就联想到可以用二分法。

能有这种反应速度值得称赞，先给自己鼓鼓掌 。

但是“有序”并不是一个应用二分查找的必要条件。你能想到为什么吗？

看这样一个问题：

有一个函数

F 的定义域是左闭右开区间

[begin, end)，值域为

{true, false}，且已知存在

mid，使得区间

[begin, mid)上的函数值为

true，区间

[mid, end)上的函数值为

false。请问你能找出

mid的值吗？

你看到这个问题，是不是觉得迷惑，好端端地在说算法二分搜索，怎么突然跳到数学上了？

其实上面两个问题之间有某种联系，不信你看：

上面的函数

F我们并不知道它具体长什么样子，但如果我们这样定义:

F(i) = (A[i] < target)，你是不是能把它和第一个问题联系起来了呢？

原来第一个问题只是第二个问题的具体化。第二个问题更加抽象，但也更有力量。

我们会发现，第二个问题的描述里，并没有提到输入数据的样子，可以是数组，但更一般化地，用区间表达；输入可以是数组，但没有要求数组元素可以比较（元素无法比较，自然也就没有“序”的概念了）。 寻找的对象变成了mid，不再是target，因为我们把target放入F的定义中了。

下面附上两种视角下的不同代码实现(python)，供读者参考。

# 第一个问题的视角def bs(arr, target):    begin, end = 0, len(arr)    while begin < end:        mid = (begin + end) // 2        if arr[mid] == target:            return mid        elif arr[mid] < target:            begin = mid + 1        else:            end = mid    return -1# 第二个问题的视角def bs2(arr, target):    def F(i):        return (arr[i] < target)        begin, end = 0, len(arr)    while begin < end:        mid = (begin + end) // 2        if F(mid):            begin = mid + 1        else:            end = mid    # After while loop, F value is true in [0, begin), false in [begin, len(arr))    if begin < len(arr) and arr[0] == target:        return begin    return -1

第二种代码实现似乎并没有比第一种能少几行代码，为什么要了解第二种视角呢？原因就在于它能减轻你的思维负担，让思路更加清晰。原本复杂的逻辑被拆分成了“定义F”，“寻找定义域的mid点”，“后续处理” 三块相对独立的模块。其中第一个模块能够分析题意得知，第二个模块可以提炼成模板记忆，第三个模块跟题目相关。

这里的例题可能没办法让你理解这种思路的好处，但当你多做了几道leetcode题目之后，你的看法会有改变。推荐几道题目：

另外，binary search的写法有很多种，我个人比较喜欢c++ stl中lower_bound的写法，但也稍做了些改变。有兴趣的可以参考下面的链接。

我还在这篇文章里解释了上面的代码，并分析了循环不变量/性质。