有趣的算法-二分查找

先理解一下什么是二分（折半）算法？先来看个有趣的例子：

一间很大的教室如果老师要点人数，有什么好方法吗？一个一个点，2个2个点其实这都是算法，如果这个教室有10000人，你怎么数呢，有一个很好的方法就是让所有同学都站起来，每个人代表数字1，然后两个人商量好一个人取得对方的数字相加，另外一个人就坐下去，以此类推，每一次都会有原来一半的人坐下去，这样不用几次剩下最后一个人他的数字就是总人数了。10000人理论上2的14次方就远远超过了，也就是14次就能数万了。

不过这个让人实现起来比较困难，因为有的人会犯错，让计算机去做反而更容易。

二分（折半）查找

假设要在电话簿中找一个名字以K打头的人，（现在谁还用电话簿！）可以从头开始翻页，直到进入以K打头的部分。但你很可能不这样做，而是从中间开始，因为你知道以K打头的名字在电话簿中间。 

又假设要在英文字典中找一个以O打头的单词，你也将从中间附近开始。

现在假设你登录某个网站。当你这样做时，网站必须核实你是否有其网站的账户，因此必须在其数据库中查找你的用户名。如果你的用户名为karlmageddon，该网站可从以A打头的部分开始查找，但更合乎逻辑的做法是从中间开始查找。

这是一个查找问题，在前述所有情况下，都可使用同一种算法来解决问题，这种算法就是二分查找。

二分查找是一种算法，其输入是一个有序的元素列表（必须有序的原因稍后解释）。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回null。

下面的示例说明了二分查找的工作原理。我随便想一个1～100的数字。

你的目标是以最少的次数猜到这个数字。你每次猜测后，我会说小了、大了或对了。 假设你从1开始依次往上猜，猜测过程会是这样。 

糟糕的猜数方法

这是简单查找，更准确的说法是傻找。每次猜测都只能排除一个数字。如果我想的数字是99，你得猜99次才能猜到！ 

更佳的查找方式 

下面是一种更佳的猜法。从 50 开始。

小了，但排除了一半的数字！至此，你知道1～50都小了。接下来，你猜75。 

大了，那余下的数字又排除了一半！使用二分查找时，你猜测的是中间的数字，从而每次都将余下的数字排除一半。接下来，你猜63（50和75中间的数字）。 

这就是二分查找算法！每次猜测排除的数字个数如下。

使用二分查找时，每次都排除一半的数字不管我心里想的是哪个数字，你在7次之内都能猜到，因为每次猜测都将排除很多数字！ 

假设你要在英文字典中查找一个单词，而该字典包含240 000个单词，你认为每种查找最多需要多少步？ 

说 明：

仅当列表是有序的时候，二分查找才管用。例如，电话簿中的名字是按字母顺序排列的，因此可以使用二分查找来查找名字。如果名字不是按顺序排列的，结果将如何呢？

其实二分查找算法也是一种分治策略的算法。

点我查看Scratch模拟二分查找在列表中查询某个数字（按空格键非递归实现  按绿旗递归实现）

Python实现二分查找

# 二分查找
# 一定要是有序的列表（升序或者降序）
# 这里把列表处理成升序排列
# 每次把列表分成一半再查找

# 非递归方法
def binarry_search(data_list, target):
    '''
    非递归
    :param data_list: 传入有序列表
    :param target:    要查找的目标数
    :return: 返回值
    '''
    # low和high表示列表中的下标 第一个和最后一个
    low = 0
    high = len(data_list) - 1   
    count = 1  # 计查找的次数
    while low <= high:
        mid = (low + high) // 2  # ‘//’表示向下取整 例如9//2等于4 
        if target == data_list[mid]:
            return '一共找了%d次，找到了目标数：%d' % (count, target)
        elif target > data_list[mid]:
            low = mid + 1
        else:
            high = mid - 1
        count += 1
    return '一共找了%d次，没有找到目标数' % count

# 递归方法
def binary_search2(alist, target):
    if len(alist) == 0:
        return '查询的数字{}不在此列表中'.format(target)
    else:
        midpoint = len(alist) // 2

        if alist[midpoint] == target:
            return '在查询的列表中找到目标数字{}'.format(target)
        else:
            if target < alist[midpoint]:
                return binary_search(alist[0:midpoint], target)
            else:
                return binary_search(alist[midpoint + 1:], target)
                        
if __name__ == '__main__':
    data = [5, 15, 16, 18, 25, 33, 89, 100, 117, 139]
    print(data_list)
    print(binarry_search(data_list, 5))   # 递归调用
    print(binarry_search2(data_list, 5))  # 非递归调用

---

分享