二分查找最简单的实现方式--python

二分查找

给定一个已排序数组:
[-1 ,0, 2, 3, 5]
目标值:
0
返回目标值下标: 1

二分查找，先找到数组的中间数mid， left+(right-left)//2, 这种写法为防止整数溢出。left =0, right=len(arr)-1

比较mid与目标值， 如果mid大于目标值，则说明目标值可能在左半部分，此时right 变成 mid-1 ， 否则left 变成mid+1

如果arr[mid] 等于目标值， 则返回下标。

当left <= right时， 循环上述过程， 时间复杂度时O(logn)

def binary_search(arr, target, left, right):
  mid = left+(right-left)//2

  while left <= right:
    if arr[mid]==target:
      return arr.index(arr[mid])

    elif arr[mid]>target:
      return binary_search(arr, target, left, mid-1)
    else:
      return binary_search(arr, target, mid+1, right)
  return -1

测试：

test=[-1, 0, 2, 4, 5, 9]
binary_search(test, 9, 0, len(test)-1)

5