2024-09-01
Python
00

目录

1 基本介绍
2 基本的二分查找
3 左边界 vs 右边界,查找相等的元素
4 难度升级,找到 x<6 的右边界
5 找到 x>5 的左边界
6 总结模板

参考:https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/wo-xie-le--9c7a4/

1 基本介绍

二分查找法(Binary Search)是一种在有序数组中查找某一特定元素的搜索算法。其基本思想是,首先将整个有序数列分成前后两部分,判断在哪个部分中可能会找到要查找的数,然后递归地在那个部分中查找。

具体来说,首先选择数列的中间元素。如果要查找的数比中间元素小,则在数列的左半部分继续查找;如果要查找的数比中间元素大,则在数列的右半部分继续查找;如果相等,则找到了要查找的数。这样一直递归进行,直到找到要查找的数或者整个数列被查找完。

二分查找法的时间复杂度为 O(log n),其中 n 是数列中的元素个数。由于其在有序数列中查找元素的时间复杂度较低,因此常用于大规模有序数列的查找。

二分查找并不简单,Knuth 大佬(发明 KMP 算法的那位)都说二分查找:思路很简单,细节是魔鬼。

  • 有哪些细节:

while循环中使用 low <= high 还是 low < high ?

if条件里写<还是<=? 是low = mid +1?

还是low = mid ?

2 基本的二分查找

基本的二分查找中有序数组里的元素没有重复数值,而二分查找的目的就是找到符合条件的下标。

比如想在有序数组 arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] 中找到元素5的index,该如何写python代码呢:

python
def binary_search(arr, x): low = 0 high = len(arr) - 1 while low <= high: # 结束条件是 low > high, 为什么不用<符号呢:因为当low=high时,还需要判断一次,不然[low,high]就会被漏掉 mid = (low + high) // 2 # 和mid=low+(high-low)//2是一样的结果,low+(high-low)//2可以防止大数溢出 if arr[mid] < x: low = mid + 1 # 在区间 [mid+1, high] 中查找 elif arr[mid] > x: high = mid - 1 # 在区间 [low, mid-1] 中查找 elif arr[mid] == x: return mid return -1 arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] x = 5 result = binary_search(arr, x) if result != -1: print(f"Element is present at index {result}") else: print("Element is not present in array")

3 左边界 vs 右边界,查找相等的元素

当有序数组中存在重复值,即是由多个元素可以满足条件,返回哪一个下标更合适呢?

比如 arr = [1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9], 找数值5,那么左边界index是4,右边界index是6。

如果有序数组中有重复值,并且你想找到左边界的下标,你可以在二分查找的基础上,做一些改变来实现这个功能。

下面的代码展示了左边界和右边界的代码:

python
def binary_search_leftright(arr, x): low = 0 high = len(arr) - 1 result = -1 while low <= high: # 结束条件是 low > high, 为什么不用<符号呢:因为当low=high时,还需要判断一次,不然[low,high]就会被漏掉 mid = (low + high) // 2 # 和mid=low+(high-low)//2是一样的结果,low+(high-low)//2可以防止大数溢出 if arr[mid] < x: low = mid + 1 # 在区间 [mid+1, high] 中查找 elif arr[mid] > x: high = mid - 1 # 在区间 [low, mid-1] 中查找 elif arr[mid] == x: result = mid # 记录符合条件的下标 # high = mid - 1 # 在区间 [low, mid-1] 中查找,这就很灵性,意味着找到了,但是还要继续找,而且趋势是往左找. 即找左边界。 low = mid + 1 # 在区间 [mid+1, high] 中查找,这就很灵性,意味着找到了,但是还要继续找,而且趋势是往右找. 即找右边界。 return result arr = [1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9] x = 5 result = binary_search_left(arr, x) if result != -1: print(f"Element is present at index {result}") else: print("Element is not present in array")

4 难度升级,找到 x<6 的右边界

在 arr = [4, 4, 5, 5, 6, 6, 7, 8, 9] 中找到一个元素x,满足x<6,且x是右边界元素:

python
def binary_search_right(arr, x): low = 0 high = len(arr) - 1 while low < high: mid = (low + high) // 2 if arr[mid] < x: low = mid + 1 # 继续在[mid+1, high]中查找,因为想找右边界 else: high = mid # 为什么不是mid-1呢? if arr[high] >= x: return high - 1 else: return high arr = [4, 4, 5, 5, 6, 6, 7, 8, 9] x = 6 result = binary_search_right(arr, x) print(result)

函数返回 high - 1 或者返回high。

  • 如果将条件改为while low <= high呢,这样不可以吗?

如果你将循环的条件改为 while low <= high,在数组中查找小于目标值的右边界的时候是会有问题的。

当low==high时,如果arr[high] >= x 那么最终返回值就是high -1,而实际上并不是小于目标值的右边界。

因此,在二分查找中查找右边界时,循环条件应该是 low < high.

这样当循环结束时,high指向的就是第一个大于等于目标值的位置,而high - 1就是小于目标值的右边界

所以,在二分查找中查找右边界时,循环条件应该是 low < high 而非 low <= high,这是为了确保查找的正确性

除此之外,还可能发生死循环。

  • 那为什么是high = mid ,而不是high = mid -1?

在查找小于目标值的右边界时,如果循环条件是 low < high, 当 arr[mid] >= x 时,如果 high = mid -1 会使得 high 不满足循环条件,从而导致循环终止,而不是移动到小于目标值的右边界。

而赋值high = mid会使得high = mid或者 high =

mid-1,这样high总是满足循环条件且正确地找到了第一个大于等于目标值的位置,而high-1就是小于目标值的右边界。

所以如果你想在查找小于目标值的右边界时,应该让 high = mid。这样可以保证查找的正确性。

5 找到 x>5 的左边界

在 arr = [4, 4, 5, 5, 6, 6, 7, 8, 9] 中找到一个元素x,满足x>5,且x是左边界元素:

python
def binary_search_left(arr, x): low = 0 high = len(arr) - 1 while low <= high: mid = (low + high) // 2 if arr[mid] <= x: low = mid + 1 else: high = mid - 1 return low arr = [4, 4, 5, 5, 6, 6, 7, 8, 9] x = 5 result = binary_search_left(arr, x) print(result)

或者:

python
def binary_search_left(arr, x): low = 0 high = len(arr) while low < high: mid = (low + high) // 2 if arr[mid] <= x: low = mid + 1 else: high = mid return low

6 总结模板

当使用 "while low <= high" 时,要想结束循环,就需要更严格的判断,从而就不需要再单独对low 和high 进行特判。

如果要查找左边界(x>5的左边界):

python
def binary_search_left(arr, x): low = 0 high = len(arr) - 1 while low <= high: mid = (low + high) // 2 if arr[mid] <= x: # 如果是x>=5,这里就需要改变查找区间 low = mid + 1 else: high = mid - 1 return low

如果要查找右边界(x<6的右边界):

python
def binary_search_right(arr, x): low = 0 high = len(arr) - 1 while low <= high: mid = (low + high) // 2 if arr[mid] < x: # 如果是x<=6,这里就需要改变查找区间 low = mid + 1 else: high = mid - 1 return high
如果对你有用的话,可以打赏哦
打赏
ali pay
wechat pay

本文作者:Dong

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 CC BY-NC。本作品采用《知识共享署名-非商业性使用 4.0 国际许可协议》进行许可。您可以在非商业用途下自由转载和修改,但必须注明出处并提供原作者链接。 许可协议。转载请注明出处!