Python 递归函数实现二分法，带思路解释

        二分法可以大大提升对有序数列的查找，传统的迭代查找会挨个比较数列中的值，如果数列较为庞大会影响查询效率。二分法每次取数列的中间数与待查找数字比较大小，以升序排列为例子 首先要考虑数列长度的奇偶性。

        奇数取中间位置的数字，如果比待查找数字大就应该往左找。此时要收缩数列的长度，把从中间数后面的数列全部‘砍掉’：newlist=oldlist[0:中间数字下标];  同理如果比待查数小就要砍掉中间数之前的数字：newlist=oldlist[中间数下标 : len(oldlist)].    备注.python中截取数列的方式是 list[起点: 终点]，终点下标截取是终点-1，如果要截取到终点需要额外+1。

        在反复二分查找的时候会生成新的数列，如果要使用递归方式实现二分就应该要传入被分割后现序列的起点和终点分别对应 ‘初始序列’的位置。如[1,2,3,4,5,6]被分成[3,4,5]后新序列的0坐标对应的是原来的坐标2——list[2]。以向右截取为例，递归时新数列下标对应的原序列长度算法应该是现数组长度的一半+传入的上次坐标（如果第一次二分上次坐标就是0）。到此时就大概了解递归这个函数每次需要传入的参数大概要四个分别为（待查找数，原起点，原终点，被遍历数列）。

        如果是偶数个的中间参数有两个，我的想法是小于比左边大于比右边，如果夹中间待查找数字不存在的情况。待查找数<中间数1 ；中间数2<待查找书；数1<待查找数<数2,返回-1查找失败。

        附上代码仅表示个人做题思路，不是标准答案。

def findnumber(number, preindex, finindex, *numbers):       # 二分法找数
    index = preindex  # 传入的上次坐标
    findex = finindex  # 终点坐标+1
    if len(numbers) % 2 == 0:       # 判断奇偶


        if numbers[int(len(numbers)/2)] == number:  
            return int(len(numbers)/2) + index
        elif numbers[int(len(numbers)/2-1)] == number:      # 判断中间两个数是否符合
            return int(len(numbers)/2-1) + index
        elif numbers[int(len(numbers)/2)] < number:         # 比待查数小往右分割
            if len(numbers)==2:     # 如果只剩两个数还是比最大的大就是找不到
                return -1
            else:   
                newnumbers = list(numbers)[int(len(numbers)/2): len(numbers)]
                return findnumber(number, index+int(len(numbers)/2),findex, *newnumbers)
        elif numbers[int(len(numbers)/2-1)] > number:
            if len(numbers)==2:         # 剩两个数还是比最小的小，找不到。
                return -1
            else:
                newnumber2 = list(numbers)[0:int(len(numbers)/2-1)]
                return findnumber(number, index, findex-int((len(numbers)-1)/2), *newnumber2)
        elif (numbers[int(len(numbers)/2-1)]<number<numbers[int(len(numbers)/2)]) and len(numbers)==2 :
                # 待查数卡中间，找不到的情况
            return -1

    else:       # 奇数

        if numbers[int((len(numbers)-1)/2)] == number:
            return int((len(numbers)-1)/2)+index
        elif numbers[int((len(numbers)-1)/2)] > number:
            if len(numbers) == 1:
                return -1
            else:
                newnumber = list(numbers)[0:int((len(numbers)-1)/2)]
                return findnumber(number, index, findex-int((len(numbers)-1)/2), *newnumber)
        elif numbers[int((len(numbers)-1)/2)] < number:
            if len(numbers) == 1:
                return -1
            else:
                newnumber2 = list(numbers)[int((len(numbers)-1)/2):len(numbers)]
                return findnumber(number, int((len(numbers) - 1) / 2) + index, findex, *newnumber2)

list1 = [1, 2, 3, 4, 5, 6, 7]
list2 = []
for i in range(0,50):
    list2.append(i)

print(findnumber(2.5, 0, len(list1), *list1))
print(findnumber(2, 0, len(list2), *list2))