二分查找及python实现

首先介绍二分查找，然后介绍其python实现（代码返回查找的次数，这也是很多笔试题会问到的）。

二分法：也称二分搜索（binary search）、折半搜索（half-interval search）、对数搜索（logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。

二分查找的实现步骤：

1.首先查找数组必须是有序的(假设为升序)。

2.取查找数组中间的数作为基准，如果这个基准等于所要查找的数则结束搜索，如果需要查找的数据大于基准说明该数存在于数组的左边。反之存在于基准右边。

3 假设待查找的数小于基准,那么将基准换成左子数组的中间的数，重复步骤2，直到找到该数。如果待查的数大于基准则将基准换成右子数组中间的数，重复步骤2.

python实现（python3）：

输入为排好序的一组数，以空格隔开。以及需要查找的数。

输出为查找次数（如果没有查找到则输出None）。

__author__ = "Allen Liu"
__time__ = "2017/8/20"
'''This program used to '''
set_in = input().split(' ') #获得输入有序数组
num_serch = int(input()) #获得需要查找的数
set_in = [int(i) for i in set_in] #将输入的字符元素转化成整数
def  binary_search(set_search, key_search):
    # 获得输入数组的排列顺序
    if set_search[len(set_search) - 1] > set_search[0]:
        ord_indicator = True  # True表示数组按照从小到大的顺序
    else:
        ord_indicator = False  # False表示数组按照从大到小的顺序
    left = 0 #给定查找的左边界初始值
    right = len(set_search) - 1 #给定查找的右边界初始值
    count = 0 #用于记录查找次数
    while left <= right:
        count += 1
        mid = (left + right) // 2
        if set_search[mid] == key_search:
            return count
        elif set_search[mid] < key_search:
            if ord_indicator == True: #注意递增数列和递减数列的操作不同
                left = mid + 1
            else:
                right = mid - 1
        else:
            if ord_indicator == True:
                right = mid - 1
            else:
                left = mid + 1
    return None #没有找到返回None

print(binary_search(set_in, num_serch))