Python二分查找

#二分查找

def binarySearch(arr, target):
    l = 0
    r = len(arr) - 1
    while(l <= r):
        # 为什么这个=号的影响这么大呢？l < r就不行呢？
        # 因为如果没有这个等号，当r和l指针重合时就进不来了。r和l重合，意味找到了，此时应该进入while把结果返回出去。
        # r和l重合的下一次迭代就该返回-1了；
        mid = (l+r)//2
        if arr[mid] == target : return mid
        if arr[mid] < target:
            l = mid + 1
        elif arr[mid] > target:
            r = mid - 1
    return -1

arr = [1,2,3,4,5,6,7,8,9,90,111]
target = 7.5
print("Index is {:d}".format(binarySearch(arr, target)))

自己蒙着头写了一遍，发现判断条件那块，总是写错。

while r<=l都应该进入循环！！！

为什么呢？因为如果没有这个等号，当r和l指针重合时就进不来了。r和l重合，意味找到了，此时应该进入while把结果返回出去。

当然还有迭代的写法，那么把l,r也都放到形式参数中去吧。

Python 二分查找 | 菜鸟教程

# 递归的解决方案

def binarySearch(arr, target, l ,r):
    if l <= r:
        mid = (l+r)//2
        if arr[mid] == target : return mid
        if arr[mid] < target:
            l = mid + 1
            return binarySearch(arr, target, l ,r) #这里总是忘记写return
        else:
            r = mid - 1
            return binarySearch(arr, target, l ,r)
    else:
        return -1

arr = [1,2,3,4,5,6,7,8,9,90,111]
l = 0
r = len(arr) - 1
target = 8
res = binarySearch(arr, target, l, r)

print("Index is {:d}".format(res))

用递归的方法，解决这个问题时，总是忘记，return 递归函数的结果

天啊！！！

我从来没有考虑过这个问题：

mid = low + (high-low) //2