二分查找算法

题目：输入指定列表和一个待查找的元素，输出元素是否在列表中，若存在则返回下标

思想：利用二分查找来做，事先需要对列表进行排序，二分查找只对有序表有效

时间复杂度：O(logn)

二分查找算法：
1. 对一个列表进行排序（默认升序）。
2. 找到中间值，判断要找的值和中间值大小的比较。
3. 如果中间值大一些，则在中间值的左侧区域继续按照上述方式查找。
4. 如果中间值小一些，则在中间值的右侧区域继续按照上述方式查找。
5. 直到找到我们希望的数字。

实现：

'''
功能：二分查找
''' 
def binary_search(num_list, x):
    num_list = sorted(num_list)   # 默认升序排序
    left, right = 0, len(num_list)
    while left < right:
        mid = (left + right) // 2   # mid = int((left + right) / 2)
        if num_list[mid] > x:
            right = mid
        elif num_list[mid] < x:
            left = mid + 1 
        else:
            return "待查元素{0}在列表中下表为：{1}".format(x, mid)
    return "待查元素%s不在制定列表中"%x
    
if __name__ == '__main__': 
    num_list = [34,6,78,9,23,56,177,33,2,6,30,99,83,21,17]
    print(binary_search(num_list, 34))
    print(binary_search(num_list, 177))
    print(binary_search(num_list, 21))
    print(binary_search(num_list, 211))
    print(binary_search(num_list, 985))