#!/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))