接着学一下二分查找(下)。
典型的二分查找问题
查找第一个值等于给定值的元素
有序数据集合中存在重复的数据,如何找到第一个值等于给定值的数据?假设数据是从小到大排列为前提。
第一种方法,比较容易理解
1 | def binary_search_left(nums: List[int], target: int) -> int: |
第二种方法,比较简洁,但是不太容易理解。
1 | def binary_search_left(nums: List[int], target: int) -> int: |
这段代码中有两个地方比较难理解,第一个是if num[mid] >= target: high = mid-1
,文章中有段评论写的比较好,可以帮助理解。当mid
等于value
时,高位还会往左移去找第一个,那么势必会带来的问题是即使找到了第一个值为value
的元素,高位还是会往左移动,但下一次判断的时候数组中已经没有值为value
的值了,这时候代码会继续循环一直到低位加一后大于高位,这时候代码会跳出循环,而此时的低位正好是高位上一个经过的值为value
的第一个元素。举例,假如有序数据集合为[1, 1, 1, 2, 2, 6, 9, 10]
,然后debug
来分析,会一目了然。第二个是low < len(nums)
,因为返回值是返回符合指定值的low
,所以要判断一下数组是否越界。那什么情况下会数组越界呢?末尾文章评论中提到一种特殊情况,如果给定的值大于任何一个数组元素,low
就会等于len(nums)
,会导致数组越界。
查找最后一个值等于给定值的元素
有序数据集合中存在重复的数据,如何找到最后一个值等于给定值的数据?假设数据是从小到大排列为前提。
仿照上一题的第一种解法:
1 | def binary_search_right(nums: List[int], target: int) -> int: |
查找第一个大于等于给定值的元素
在有序数组中,查找第一个大于等于给定值的元素。比如,数组中存储的这样的一个序列,3, 4, 6, 7, 10
。如果查找第一个大于等于5的元素,那就是6。
1 | def binary_search_left_no_less(nums: List[int], target: int) -> int: |
查找最后一个小于等于给定值的元素
查找最后一个小于等于给定值的元素。比如,数组中存储了这样一组数据:3, 5, 6, 8, 9, 10
。最后一个小于等于7的元素就是6。
1 | def binary_search_right_no_less(nums: List[int], target: int) -> int: |
解答开篇
如何快速定位出一个IP地址的归属地?这里我反复读了好几遍,没有理解文章的含义。
文章主要是通过这个问题引出第四种变形问题“在有序数组中,查找最后一个小于等于给定值的元素”。
内容小结
二分查找更适合用在“近似”查找问题,在这类问题上,二分查找的优势更加明显。
除了前面涉及到的这四道题目,二分查找的变形问题其实还可以有很多,比如“查找第一个小于等于给定值的元素”,“查找最后一个大于等于给定值的元素”。相比二分查找问题,二分查找变形问题的关键在于,low
和high
的更新。
课后思考
如果有序数组是一个循环有序数组,比如4, 5, 6, 1, 2, 3
。针对这种情况,如何实现一个求“值等于给定值”的二分查找算法?
第一种方法
找到分界下标,分成两个有序数组。
判断目标值在哪个有序数据范围内,做二分查找。
时间复杂度\(O(n)\)
第二种方法
找到最大值的下标
x
;所有元素下标
+x
偏移,超过数组范围值的取模;利用偏移后的下标做二分查找;
如果找到目标下标,再做
-x
操作,就是目标值实际下标。
时间复杂度\(O(n)\)
第三种方法
以数组中间点分区,会将数组分成一个有序数组和一个循环有序数组。
如果首元素小于
mid
,说明前半部分是有序的,后半部分是循环有序数组。如果首元素大于
mid
,说明前半部分是循环有序数组,后半部分是有序的。
如果目标元素在有序数组范围中,使用二分查找。
如果目标元素在循环有序数组中,递归以上操作,直到目标元素出现在有序数组范围中。
这种方式相当于两次二分查找,时间复杂度为\(O(logn)\)