二分查找（下）
2020-03-05 本文已影响0人
leejnull
4种常见的二分查找变形问题
- 查找第一个值等于给定值的元素
- 查找最后一个值等于给定值的元素
- 查找第一个大于等于给定值的元素
- 查找最后一个小于等于给定值的元素
查找第一个值等于给定值
这里都默认数据是从小到达有序排序。
def search_first_equal(array, value):
low = 0
high = len(array) - 1
while low <= high:
mid = low + ((high-low)>>1)
if array[mid] == value:
if mid == 0 or array[mid-1] != value:
return mid
else:
high = mid - 1
elif array[mid] < value:
low = mid + 1
else:
high = mid - 1
return -1
思路是在找到mid的值等于value时，我们要知道mid之前是否有相同值的数据，那怎么判断呢：如果mid==0，那么说明在它前面没有元素了， 返回mid；如果mid前一个元素不等于value，那么该mid就是对应第一个值的元素位置。
查找最后一个值等于给定值的元素
def search_last_equal(array, value):
low = 0
high = len(array) - 1
while low <= high:
mid = low + ((high-low)>>1)
if array[mid] == value:
if mid == len(array)-1 or array[mid+1] != value:
return mid
else:
low = mid + 1
elif array[mid] < value:
low = mid + 1
else:
high = mid - 1
return -1
这个就很简单了，理解了前面的思路就行。
查找第一个大于等于给定值的元素
def search_first_greater_or_equal(array, value):
low = 0
high = len(array) - 1
while low <= high:
mid = low + ((high-low)>>1)
if array[mid] >= value:
if mid == 0 or array[mid-1] < value:
return mid
else:
high = mid - 1
else:
low = mid + 1
return -1
查找最后一个小于等于给定值的元素
def search_last_less_or_equal(array, value):
low = 0
high = len(array) - 1
while low <= high:
mid = low + ((high-low)>>1)
if array[mid] <= value:
if mid == len(array) - 1 or array[mid+1] > value:
return mid
else:
low = mid + 1
else:
high = mid - 1
return -1
