基本概念

当我们要从一个序列中查找一个元素的时候,二分查找是一种非常快速的查找算法,二分查找又叫折半查找。它对要查找的序列有两个要求,一是该序列必须是有序的(即该序列中的所有元素都是按照大小关系排好序的,升序和降序都可以,本文假设是升序排列的),二是该序列必须是顺序存储的。下图展示的就是一个能进行二分查找的序列。

如果一个序列是无序的或者是链表,那么该序列就不能进行二分查找。之所以被查找的序列要满足这样的条件,是由二分查找算法的原理决定的

算法原理

二分查找算法的原理如下:

  1. 如果待查序列为空,那么就返回-1,并退出算法;这表示查找不到目标元素
  2. 如果待查序列不为空,则将它的中间元素与要查找的目标元素进行匹配,看它们是否相等
  3. 如果相等,则返回该中间元素的索引,并退出算法;此时就查找成功了
  4. 如果不相等,就再比较这两个元素的大小
  5. 如果该中间元素大于目标元素,那么就将当前序列的前半部分作为新的待查序列;这是因为后半部分的所有元素都大于目标元素,它们全都被排除了
  6. 如果该中间元素小于目标元素,那么就将当前序列的后半部分作为新的待查序列;这是因为前半部分的所有元素都小于目标元素,它们全都被排除了
  7. 在新的待查序列上重新开始第1步的工作

二分查找之所以快速,是因为它在匹配不成功的时候,每次都能排除剩余元素中一半的元素。因此可能包含目标元素的有效范围就收缩得很快,而不像顺序查找那样,每次仅能排除一个元素

算法模板

区间定义:[l, r) 左闭右开
其中f(m)函数代表找到了满足条件的情况,如果存在就返回对应的位置
如果没有找到,就通过g(m)函数缩小查找的范围,继续查找

def binary_search(l, r):
    while l < r:
        m = l + (r - l) // 2
        if f(m):      # 判断找了没有 (可选)
            return m
        if g(m):      # 根据题目条件设置g(m)的策略
            r = m     # 新的查找范围 [l, m)
        else:
            l = m + 1 # 新的查找范围 [m+1, r)
    return -1          # 还是没有找到 返回-1

为什么二分查找的left=mid+1,不能是left=mid?

这个和定义的区间有关,我们定义的查找的区间是[l, r),即左闭右开。即每次查找的范围已经包括了 left, 但是不包括 right。而mid的位置已经计算过了,所以下次不需要再判断mid。那么下次搜索的范围是[mid + 1, right)


当序列中出现重复元素的时候,我们可以根据题目要求选择对应的模板进行解决
重复元素的区间:[lower_bound,upper_bound)

lower_bound(重复元素的下界): 当搜索的索引值对应的元素,大于等于目标值的时候,返回索引( nums[i] >= x )

def lowwer_bound(nums, target):
    # find in range [left, right)
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] >= target: # g(m)
            right = mid
        else:
            left = mid + 1
    return left

upper_bound(重复元素的上界,需要将其索引减一): 当搜索的索引值对应的元素,大于目标值的时候,返回索引( nums[i] > x )

def upper_bound(nums, target):
    # find in range [left, right)
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] > target: # g(m)
            right = mid
        else:
            left = mid + 1
    return left

比如我们现在有这样一个数组:nums = [1,2,2,2,4,4,5]
lower_bound(nums,2) = 1 , upper_bound(nums,2) = 4
lower_bound(nums,3) = 4 通过判断当前索引的元素是否等于3,确定这个元素是否存在


还有一个细节需要注意

通过上面的模板代码我们可以知道,取中间值的式子为:mid = left + (right - left) // 2
那么,为什么不是:mid = (left+right) // 2

是因为在Java等编程语言中,当(left+right)很大的时候,会出现整型数值溢出的问题,数小的时候其实没问题
在Python中其实不用考虑这个问题,Python的整型是没有限制大小的,但实际上由于机器内存的有限,我们使用的整数是不可能无限大的

所以如果你使用的Python语言做此类的算法题,取中间值的式子你用什么都可以,但是在其他编程语言中需要考虑整数数值溢出的问题

二分查找(经典例题)

题目:给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target
写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1

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

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

解题思路

利用”二分查找”的思想,先找数组最中间的元素,判断其与target值的大小关系
如果该值大于target那么就选择搜索区间的左半部分继续搜索,
反之如果该值小于target那么就将搜索区间的右半部分继续搜索,
如果最终搜索区间的左右节点重合也未找到target,则表明不存在该值返回-1

class Solution:
    def search(self, nums, target) -> int:
        left,right = 0,len(nums)
    
        while left < right:
            mid = left + (right-left)//2
            if nums[mid] == target:
                return mid
            if nums[mid] > target:
                right = mid
            else:
                left = mid+1
        return -1

x 的平方根

实现 int sqrt(int x) 函数
计算并返回 x 的平方根,其中 x 是非负整数
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去

示例 1:
输入: 4
输出: 2

示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数,小数部分将被舍去。

解题思路

我们只需要在0-(x+1)的范围内找到一个数,满足m * m = x 即可满足题目要求,返回m的值即可
为什么搜索的范围是0-(x+1),取决于我们的搜索区间[l,r)

class Solution:
    def mySqrt(self, x: int) -> int:
        left,right = 0,x

        while left<right:
            mid = left+(right-left)//2
            if mid**2 == x:
                return mid
            if mid**2 > x:
                right = mid
            else:
                left = mid+1
        return left-1

为什么函数的返回值是 left-1
当出现某个整数的平方根带小数的时候,最后的结果就是left-1
比如这个数是8,那么他的平方根就是 2.82842...,传入函数中,最后的left会是3
因为在while循环中,不可能存在一个整数的平方等于8
当3(left)<3(right)的时候,也就是停止while循环的时候
此时解肯定不是left,而left是mid+1更新而来,上一个mid恰好满足mid*mid<x
所以,left-1的结果就是sqrt(8)的结果

爱吃香蕉的珂珂

珂珂喜欢吃香蕉。这里有 N 堆香蕉,第 i 堆中有 piles[i] 根香蕉。
警卫已经离开了,将在 H 小时后回来。

珂珂可以决定她吃香蕉的速度 K (单位:根/小时)。
每个小时,她将会选择一堆香蕉,从中吃掉 K 根。
如果这堆香蕉少于 K 根,她将吃掉这堆的所有香蕉,
然后这一小时内不会再吃更多的香蕉。  

珂珂喜欢慢慢吃,但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 H 小时内吃掉所有香蕉的最小速度 K(K 为整数)。

示例 1:
输入: piles = [3,6,7,11], H = 8
输出: 4

示例 2:
输入: piles = [30,11,23,4,20], H = 5
输出: 30

解题思路

连续的空间线性搜索,这就是二分查找可以发挥作用的标志
“如果香蕉小于K根,她将吃掉这堆的所有,并一小时内不会再吃更多香蕉”
所以我们最大值选择这个列表的max值即可

在这道题目中,我们还需要写一个函数,通过传入速度K,返回吃掉所有香蕉的用时t
再与题目给出的的H进行对比,最后返回答案即可

class Solution:
    def minEatingSpeed(self, piles, h) -> int:
        def cost(k):
            t = 0
            for pile in piles:
                t += int(pile / k)
                if pile % k != 0:
                    t += 1
            return t

        left,right = 1,max(piles)
        while left<right:
            mid = left+(right-left)//2
            
            if cost(mid) <= h:
                right = mid
            else:
                left = mid+1
        return left
世界因代码而改变 Peace Out
最后修改:2021 年 12 月 26 日 10 : 05 AM
如果觉得我的文章对你有用,请随意赞赏