关于二分查找

二分查找 (binary search) ,是在有序数组中查找某一特定元素的搜索算法。

有序数组是二分查找的前提条件,如果数据结构是由链表构成,使用二分查找只会事倍功半。

其原理是将查找元素跟区间中间的元素对比,将待查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为0。

假设数据集为n,每次查找后数据减少一半,如图,其中可知k=log2n,

所以二分查找的时间复杂度为 O(logn), 并且不需要额外空间,空间复杂度为 O(1)

二分查找基本实现

有序数组不存在重复元素

非递归

1
2
3
4
5
6
7
8
9
10
11
def binary_search(nums, n):
low, high = 0, len(nums) - 1
while low <= high:
mid = (low + high) // 2
if nums[mid] < n:
low = mid + 1
elif nums[mid] > n:
high = mid - 1
else:
return mid
return -1

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
def binary_search(nums, n):
return _search(nums, 0, len(nums) - 1, n)

def _search(nums, low, high, n):
if low > high:
return -1
mid = (low + high) // 2
if nums[mid] < n:
return _search(nums, mid+1, high, n)
elif nums[mid] > n:
return _search(nums, low, mid-1, n)
else:
return mid

二分查找变种的实现

基本实现中的事例有个前提条件需要数组不存在重复元素,当给定的数组中包含重复的元素时,并且有查找元素条件时,使用上面事例代码查找,显然不能达到要求,不过稍加修改就可以使用,以下是4道变形题。

查找第一个值等于给定值的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def bs_first(nums, n):
low, high = 0, len(nums) - 1
while low <= high:
mid = (low + high) // 2
if nums[mid] > n:
high = mid - 1
elif nums[mid] < n:
low = mid + 1
else: # nums[mid] == n
if mid == 0 or nums[mid - 1] < n:
return mid
else:
high = mid - 1
return -1

查找最后一个值等于给定值的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def bs_last(nums, n):
low, high = 0, len(nums) - 1
while low <= high:
mid = (low + high) // 2
if nums[mid] > n:
high = mid - 1
elif nums[mid] < n:
low = mid + 1
else: # nums[mid] == n
if mid == len(nums) - 1 or nums[mid + 1] > n:
return mid
else:
low = mid + 1
return -1

以上两道变形题,查找重复元素中的第一个值(最后一个值),如代码所示,只需要在nums[mid] == n分支,多一个判断,查看前一位(后一位)是不是指定值,如果是则继续查找。


查找第一个大于或等于给定值的元素

优先查找第一个等于给定值元素,如果不存在,则查找第一个大于该值的元素

1
2
3
4
5
6
7
8
9
10
11
12
def bs_first_equal_or_gather(nums, n):
low, high = 0, len(nums) - 1
while low <= high:
mid = (low + high) // 2
if nums[mid] >= n:
if mid == 0 or nums[mid - 1] < n:
return mid
else:
high = mid - 1
elif nums[mid] < n:
low = mid + 1
return -1

查找最后一个小于或等于给定值的元素

优先查找最后一个等于给定值元素,如果不存在,则查找最后一个小于该值的元素

1
2
3
4
5
6
7
8
9
10
11
12
def bs_last_equal_or_less(nums, n):
low, high = 0, len(nums) - 1
while low <= high:
mid = (low + high) // 2
if nums[mid] > n:
high = mid - 1
elif nums[mid] <= n:
if mid == len(nums) - 1 or nums[mid + 1] > n:
return mid
else:
low = mid + 1
return -1

以上两道变形题,只需要注意该值 是不是 大于等于 (小于等于) 给定值,如果是,再判断该值的上一个值小于 (下一个值大于)给定值, 如果是则返回该值。

总结

二分查找相对于其他算法简单,不过要想写出对的二分查找,需要注意一下几点。

  1. 循环的退出条件,low <= high

  2. 每种条件的判断,以及low,high的更新,一般的变形题只需要更改判断条件及区间的更新即可;

  3. 中间值mid的取值,如果在low,high 值较大时,可使用位运算进行优化 mid = low + ((high - low) >> 1)