算法：二分查找（python版）

#!/usr/bin/env python
#coding -*- utf:8 -*-
#二分查找
#时间复杂度O（logn）
#一个时间常量O（1）将问题的规模缩小一半，则O(logn)


import random

def binary_search(arraya, x, N):
    low = 0
    high = N-1
    notfound = -1

    while low<=high:
        #这里是//2，写一个/会出错，因为python3中3/2=1.5，3//2=1
        middle = (low+high)//2
        if(arraya[middle] < x):
            low = middle + 1
        #注意这里是elif，一开始我写成了if会出错
        elif(arraya[middle] > x):
            high = middle - 1
        else:
            return middle
    return notfound

if __name__=='__main__':
    n = int(input("所要生成数组的长度："))
    a = []
    for i in range(n):
        x = random.choice(range(100))
        a.append(x)
    #这里排序就用内置的吧！
    #列表可以被修改
    a.sort()
    print("生成的数组(从小到大)：",a)
    b = int(input("想要查找的x值为："))
    if(binary_search(a, b, n)==-1):
        print("所要查找的x不在该数组里！")
    else:
        print("x的下标为", binary_search(a, b, n))