二分查找的变形

发表于 | 分类于 | 阅读次数 ℃
本文字数： 1.5k | 阅读时长 ≈ 1 分钟

同样是基于有序数据的二分查找，但是当数据中存在相同数据的时候，用上一版的二分查找找到的索引可能不是你想要的，所以存在以下二分查找的四类变形：

  • 查找第一个等于给定值的索引
  • 查找最后一个等于给定值的索引
  • 查找第一个大于等于给定值的索引
  • 查找最后一个小于等于给定值的索引

查找第一个等于给定值的索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def main(arr, value):
	low = 0
	high = len(arr) - 1

	while low <= high:
		mid = low + ((high - low)>> 1)
		if arr[mid] > value:
			high = mid - 1
		elif arr[mid] < value:
			low = mid + 1
		else: 
			# 在所有等于给定值得数据中再进行处理
			# mid = 0肯定是第一个索引了，所以直接返回
			# 当mid的前一位不等于目标值时，mid满足条件
			if mid == 0 or arr[mid-1] != value:
				return mid
			else:
				high = mid - 1

查找最后一个等于给定值的索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def main(arr, value):
	low = 0
	high = len(arr) - 1

	while low <= high:
		mid = low + ((high - low)>> 1)
		if arr[mid] > value:
			high = mid - 1
		elif arr[mid] < value:
			low = mid + 1
		else:
			# 当mid 等于最大索引时，满足条件，可以直接返回
			# 当mid的下一位不等于给定值时，mid肯定是最后一个满足给定值得索引，所以返回
			if mid == len(arr) - 1 or arr[mid+1] != value:
				return mid
			else:
				low = mid + 1
	return -1

查找第一个大于等于给定值的索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def main(arr, value):
	low = 0
	high = len(arr) - 1

	while low <= high:
		mid = low + ((high - low) >> 1)
		if arr[mid] < value:
			low = mid + 1
		else:
			# 在所有大于等于给定值的数据中再行处理
			# 前一位小于给定值时，当前索引肯定是第一个大于等于给定值得索引
			if mid == 0 or arr[mid-1] < value:
				return mid 
			else:
				high = mid - 1
	return -1

查找最后一个小于等于给定值的索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def main(arr, value):
	low = 0
	high = len(arr) - 1

	while low <= high:
		mid = low + ((high - low) >> 1)
		if arr[mid] > value:
			high = mid - 1
		else:
			# 在所有小于等于给定值的元素中操作，当找出的mid的后一个大于给定元素，则此mid为最终目标
			if mid == len(arr) - 1 or arr[mid+1] > value:
				return mid
			else:
				low = mid + 1
	return -1