Violin's Blog
0%

二分查找(下)

发表于 分类于 本文字数： 3.5k 阅读时长 ≈ 9 分钟

接着学一下二分查找（下）。

典型的二分查找问题

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

有序数据集合中存在重复的数据，如何找到第一个值等于给定值的数据？假设数据是从小到大排列为前提。

第一种方法，比较容易理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def binary_search_left(nums: List[int], target: int) -> int:
    low, high = 0, len(nums)-1

    while low <= high:
        mid = low + ((high - low) >> 1)

        if nums[mid] > target:
            high = mid - 1
        elif nums[mid] < target:
            low = mid + 1
        else:
            # 如果是首元素或者前一个元素不为target
            if mid == 0 or nums[mid-1] != target:
                return mid
            else:
                high = mid - 1
    return -1
    
    
if __name__ == '__main__':
    a = [1, 1, 2, 2, 5, 6, 9, 10]
    print(binary_search_left(nums=a, target=2))  # 2

第二种方法，比较简洁，但是不太容易理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def binary_search_left(nums: List[int], target: int) -> int:

    low, high = 0, len(nums) - 1

    while low <= high:

        mid = low + (high - low) // 2

        if nums[mid] >= target:
            high = mid - 1
        else:
            low = mid + 1

    if low < len(nums) and nums[low] == target:
        return low
    return -1

这段代码中有两个地方比较难理解，第一个是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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def binary_search_right(nums: List[int], target: int) -> int:

    low, high = 0, len(nums) - 1

    while low <= high:

        mid = low + ((high - low) >> 1)

        if nums[mid] > target:
            high = mid - 1
        elif nums[mid] < target:
            low = mid + 1
        else:
            # 如果是末尾元素或者下一个元素不为target
            if mid == len(nums) - 1 or nums[mid+1] != target:
                return mid
            low = mid + 1


if __name__ == '__main__':
    a = [1, 1, 1, 2, 2, 6, 9, 10]
    print(binary_search_right(nums=a, target=2))  # 4
    print(binary_search_right(nums=a, target=1))  # 2

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

在有序数组中，查找第一个大于等于给定值的元素。比如，数组中存储的这样的一个序列，3, 4, 6, 7, 10。如果查找第一个大于等于5的元素，那就是6。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def binary_search_left_no_less(nums: List[int], target: int) -> int:
    low, high = 0, len(nums) - 1

    while low <= high:

        mid = low + ((high - low) >> 1)

        if nums[mid] >= target:
            # 如果是首元素或者前一个元素小于target
            # 注意边界条件mid==0
            if nums[mid-1] < target or mid == 0:
                return mid
            high = mid - 1
        else:
            low = mid + 1


if __name__ == '__main__':
    a = [1, 1, 1, 2, 2, 6, 9, 10]
    print(binary_search_left_no_less(nums=a, target=1))  # 0
    print(binary_search_left_no_less(nums=a, target=2))  # 3
    print(binary_search_left_no_less(nums=a, target=5))  # 5

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

查找最后一个小于等于给定值的元素。比如，数组中存储了这样一组数据：3, 5, 6, 8, 9, 10。最后一个小于等于7的元素就是6。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def binary_search_right_no_less(nums: List[int], target: int) -> int:
    low, high = 0, len(nums) - 1

    while low <= high:
        mid = low + ((high - low) >> 1)

        if nums[mid] <= target:
            # 如果是末尾元素或者下一个元素大于target
            if mid == (len(nums)-1) or nums[mid+1] > target:
                return mid
            low = mid + 1
        else:
            high = mid - 1


if __name__ == '__main__':
    a = [1, 1, 1, 2, 2, 6, 9, 10]
    print(binary_search_right_no_less(nums=a, target=1))  # 2
    print(binary_search_right_no_less(nums=a, target=4))  # 4

解答开篇

如何快速定位出一个IP地址的归属地？这里我反复读了好几遍，没有理解文章的含义。

文章主要是通过这个问题引出第四种变形问题“在有序数组中，查找最后一个小于等于给定值的元素”。

内容小结

二分查找更适合用在“近似”查找问题，在这类问题上，二分查找的优势更加明显。

除了前面涉及到的这四道题目，二分查找的变形问题其实还可以有很多，比如“查找第一个小于等于给定值的元素”，“查找最后一个大于等于给定值的元素”。相比二分查找问题，二分查找变形问题的关键在于，low和high的更新。

课后思考

如果有序数组是一个循环有序数组，比如4, 5, 6, 1, 2, 3。针对这种情况，如何实现一个求“值等于给定值”的二分查找算法？

第一种方法

  1. 找到分界下标，分成两个有序数组。

  2. 判断目标值在哪个有序数据范围内，做二分查找。

时间复杂度\(O(n)\)

第二种方法

  1. 找到最大值的下标x；

  2. 所有元素下标+x偏移，超过数组范围值的取模；

  3. 利用偏移后的下标做二分查找；

  4. 如果找到目标下标，再做-x操作，就是目标值实际下标。

时间复杂度\(O(n)\)

第三种方法

以数组中间点分区，会将数组分成一个有序数组和一个循环有序数组。

  • 如果首元素小于mid，说明前半部分是有序的，后半部分是循环有序数组。

  • 如果首元素大于mid，说明前半部分是循环有序数组，后半部分是有序的。

如果目标元素在有序数组范围中，使用二分查找。

如果目标元素在循环有序数组中，递归以上操作，直到目标元素出现在有序数组范围中。

这种方式相当于两次二分查找，时间复杂度为\(O(logn)\)

您的支持将鼓励我继续创作！