二分查找及几种变体的Python实现
1. 在不重复的有序数组中，查找等于给定值的元素
循环法
python">def search(lst, target): n = len(lst)
if n == 0:
return -1
low = 0
high = n - 1
while low <= high:
mid = (high-low)//2 + low
if lst[mid] == target:
return mid
elif lst[mid] < target:
low = mid +1
elif lst[mid] > target:
high = mid -1
return -1
递归法
def search2(lst, target, low, high): if low > high:
return -1
mid = (high-low)//2 + low
if lst[mid] == target:
return mid
elif lst[mid] < target:
return search2(lst, target, mid+1, high)
elif lst[mid] > target:
return search2(lst, target, low, mid-1)
2. 查找第一个值等于给定值的元素
def bsearch(lst, value): n = len(lst)
if n == 0:
return -1
low = 0
high = n - 1
while low <= high:
mid = (high-low) // 2 + low
if lst[mid] < value:
low = mid + 1
elif lst[mid] > value:
low = mid - 1
elif lst[mid] == value:
if mid == 0 or lst[mid-1] != value:
return mid
else:
high = mid - 1
return -1
3. 查找最后一个值等于给定值的元素
def bsearch(lst, value): n = len(lst)
if n == 0:
return -1
low = 0
high = n - 1
while low <= high:
mid = (high-low) // 2 + low
if lst[mid] > value:
high = mid - 1
elif lst[mid] < value:
low = mid + 1
elif lst[mid] == value:
if mid == n-1 or lst[mid+1] != value:
return mid
else:
low = mid + 1
return -1
4. 查找第一个大于等于给定值的元素
def bsearch(lst, value): n = len(lst)
if n == 0:
return -1
low = 0
high = n - 1
while low <= high:
mid = (high-low) // 2 + low
if lst[mid] < value:
low = mid + 1
elif lst[mid] >=value:
if mid == 0 or lst[mid-1] < value:
return mid
high = mid - 1
5. 查找最后一个小于等于给定值的元素
def bsearch(lst, value): n = len(lst)
if n == 0:
return -1
low = 0
high = n - 1
while low <= high:
mid = (high-low) // 2 + low
if lst[mid] > value:
high = mid - 1
elif lst[mid] <= value:
if mid == n-1 or lst[mid+1] > 0:
return mid
low = mid + 1
return -1
以上是 二分查找及几种变体的Python实现 的全部内容， 来源链接： utcz.com/z/389312.html
