day4 递归二分法查找

    现有一个序列，data=[for i in range(1,5000,3)],现在要求看一个数是否在列表中存在，我们知道，我们可以使用in或__contains__()的方法，判断一个值是否在列表中，但是列表也是一个一个遍历，看是否与列表中的某个值相等，如果不等则返回False；如果在，则返回True。

def binary_search(data,find_n):    mid_n = int(len(data)/2)    #递归必须有结束条件，这里的结束条件是，当只有两个长度的时候必须结束    if mid_n > 1:     #递归的结束条件，如果只有两个元素的时候就没有必要进行再一次判断了        if data[mid_n] > find_n:         #如果中间值大于查找值，说明在列表的左侧            print(data[:mid_n])            binary_search(data[:mid_n],find_n)     #再次进行递归，缩小范围        elif data[mid_n] < find_n:                 #如果中间值小于查找值，说明在中间值的右侧            print(data[mid_n:])            binary_search(data[mid_n:],find_n)     #递归，缩小范围        elif data[mid_n] == find_n:                #如果中间值等于查找值，说明在列表中            print("%s在列表data中" %find_n)    elif mid_n == 1:        #我们知道，递归结束的时候，有两种情况，第一种是长度等于2，另外一种情况是长度等于3        print(data)        if len(data) == 2:                         #如果列表长度等于2，那么就判断是否有一个等于查找值，            if data[0] == find_n or data[1] == find_n:                      print("%s在列表data中" % find_n)            else:                print("%s不在列表data中" % find_n)        else:            #列表长度等于3的时候的情况，逐个进行比较            if data[0] == find_n or data[1] == find_n or data[2] == find_n:                print("%s在列表data中" %find_n)            else:                print("%s不在列表data中" %find_n)if __name__ == "__main__":    data = [i for i in range(1,5008,4)]    binary_search(data,10)

    上面流程图中，详细描述了代码运转的过程，我们知道，如果使用递归，那么遍历列表的时候只有两种情况，要么查找的值在列表中，要么不在列表中，并且，到最后，列表的长度只可能为1和2，这个时候我们要分情况去考虑，上面总共有三种情况出现，（1）遍历过程中中间值正好就是我们要查找的值；（2）列表长度为1，那最后剩下的元素进行比较，这个时候一半就是小于等于最小值或者大于等于最大值；（3）列表的长度为2，这个时候情况也一样，要么大于等于最大值，小于等于最小值；出现列表1和2长度的原因是data原数据的长度有关，因为原数据有长度有单数和偶数之分，因此结果也会出现这两种情况，上述三种情况都要具体分析，不然肯定会报错。有些人可能输入的本来就是列表中的值肯定可以找的到，但如果不是的时候会报错。又或者奇数的时候对，偶数的时候错；偶数的时候对，奇数的时候错。