欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分查找细节探索

程序员文章站 2024-03-20 17:14:58
...

什么是二分查找

如何在一个有序数列中准确找到一个元素的位置?这时可以利用二分查找。二分查找又叫作对半查找,每次查找后,查找的范围都折半,这样查找到最后,超找范围就只剩一个数,判断它是否为要查找的数,如果是,就记录它的位置,如果不是,则要查找的数不在这个数组中。

  • 例1 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。(例题选自LeetCode官网,链接: https://leetcode-cn.com/study-plan/algorithms/?progress=9dlc1ls

  • 输入: nums = [-1,0,3,5,9,12], target = 9
    输出: 4
    解释: 9 出现在 nums 中并且下标为 4

  • 输入: nums = [-1,0,3,5,9,12], target = 2
    输出: -1
    解释: 2 不存在 nums 中因此返回 -1

如果不采用二分查找的方法,代码如下

nums = [-1, 0, 3, 5, 9, 12]
target = -2
for i in range(0, len(nums)):
    if target == nums[i]:
        print(i)
        break
    elif target > nums[i]:
        continue
    else:
        print(-1)
        break
else:
    print(-1)

可以看到从序列开始的元素寻找,如果要寻找的数字比较大时,要寻找整个序列。
下面采用二分查找的方法。

nums = [-1, 0, 3, 5, 9, 12]
target = 13
head, tail = 0, len(nums) - 1
while head <= tail:
    mid = head + (tail - head) // 2
    if target < nums[mid]:
        tail = mid - 1
    elif target > nums[mid]:
        head = mid + 1
    else:
        print(mid)
        break
else:
    print(-1)

结果为

>>>-1

在二分查找中需要注意的问题有搜索区间数组长度循环退出条件。以上程序中采用左闭右闭的情况,则其寻找范围为[0 len-1],此时while循环中应该包括=。当采用左闭右开的形式时,代码如下

nums = [-1, 0, 3, 5, 9, 12]
target = 3
head, tail = 0, len(nums)
while head < tail:
    mid = head + (tail - head) // 2
    if target > nums[mid]:
        head = mid + 1
    else:
        tail = mid
else:
    if head == len(nums):
        print(-1)
    elif target == nums[head]:
        print(head)
    else:
        print(-1)

此时需要单独判断是否出了边界。搜索范围[0 len),此时while循环中不包括=。
下面再看一个例子。

  • 例2 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。(例题选自LeetCode官网,链接: https://leetcode-cn.com/study-plan/algorithms/?progress=9dlc1ls
  • 输入: nums = [1,3,5,6], target = 5
    输出: 2
  • 输入: nums = [1,3,5,6], target = 2
    输出: 1

使用左闭右闭区间

nums = [1,3,5,6], target = 5
head, tail = 0, len(nums) - 1
while head <= tail:
    mid = head + (tail - head) // 2
    if target > nums[mid]:
        head = mid + 1
    elif target == nums[mid]:
        print(mid)
        break
    else:
        tail = mid - 1
else:
    print(head)

使用左闭右开区间

nums = [1,3,5,6], target = 5
head, tail = 0, len(nums)
while head < tail:
    mid = head + (tail - head) // 2
    if target > nums[mid]:
        head = mid + 1
    elif target == nums[mid]:
        print(mid)
        break
    else:
        tail = mid
else:
    print(tail)