目录
  1. 1. 前言
  2. 2. 二分查找
    1. 2.1. 原理
    2. 2.2. 局限性
      1. 2.2.1. 二分查找依赖数组结构
      2. 2.2.2. 二分查找针对的是有序数据
      3. 2.2.3. 数据量太小不适合二分查找
      4. 2.2.4. 数据量太大不适合二分查找
    3. 2.3. 代码模板
      1. 2.3.1. 中间值计算
      2. 2.3.2. 未成功查找的返回值
      3. 2.3.3. 循环
      4. 2.3.4. 递归
      5. 2.3.5. 变形
        1. 2.3.5.1. 查找第一个等于给定值的元素
        2. 2.3.5.2. 查到第一个大于给定值的元素
  3. 3. 69-x的平方根
    1. 3.1. 题目
    2. 3.2. 题解
  4. 4. 744-寻找比目标字母大的最小字母
    1. 4.1. 题目
    2. 4.2. 题解
  5. 5. 540-有序数组中的单一元素
    1. 5.1. 题目
    2. 5.2. 题解
  6. 6. 278-第一个错误的版本
    1. 6.1. 题目
    2. 6.2. 题解
  7. 7. 153. 寻找旋转排序数组中的最小值
    1. 7.1. 题目
    2. 7.2. 题解
  8. 8. 34-在排序数组中查找元素的第一个和最后一个位置
    1. 8.1. 题目
    2. 8.2. 题解
leetcode-二分查找

前言

 回顾一下二分查找算法,并完成leetcode二分查找的经典题。

  • 69-x的平方根
  • 744-寻找比目标字母大的最小字母
  • 540-有序数组中的单一元素
  • 278-第一个错误的版本
  • 153-寻找旋转排序数组中的最小值
  • 34-在排序数组中查找元素的第一个和最后一个位置

二分查找

参考:

https://juejin.im/post/5d510f76f265da039a287a30(下述二分内容出处)

https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/(leetcode大佬对二分查找的详细分析)

原理

 二分查找(Binary Search)算法,也叫折半查找算法。二分查找的思想非常简单,有点类似分治的思想。二分查找针对的是一个有序的数据集合,每次都通过跟区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为 0。

  • 时间复杂度:O(logn)
  • 比很多O(1)的速度都要快,因为O(1)可能标示一个非常大的数值,如O(1000)。
    • 有序数据:[1,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59],查找37
    • 二分查找需要3步
    • 顺序遍历需要11步。

局限性

二分查找依赖数组结构

 二分查找需要利用下标随机访问元素,如果我们想使用链表等其他数据结构则无法实现二分查找。

二分查找针对的是有序数据

 二分查找需要的数据必须是有序的。如果数据没有序,我们需要先排序,排序的时间复杂度最低是 O(nlogn)。所以,如果我们针对的是一组静态的数据,没有频繁地插入、删除,我们可以进行一次排序,多次二分查找。这样排序的成本可被均摊,二分查找的边际成本就会比较低。

 但是,如果我们的数据集合有频繁的插入和删除操作,要想用二分查找,要么每次插入、删除操作之后保证数据仍然有序,要么在每次二分查找之前都先进行排序。针对这种动态数据集合,无论哪种方法,维护有序的成本都是很高的。

 所以,二分查找只能用在插入、删除操作不频繁,一次排序多次查找的场景中。针对动态变化的数据集合,二分查找将不再适用。

数据量太小不适合二分查找

 如果要处理的数据量很小,完全没有必要用二分查找,顺序遍历就足够了。比如我们在一个大小为 10 的数组中查找一个元素,不管用二分查找还是顺序遍历,查找速度都差不多,只有数据量比较大的时候,二分查找的优势才会比较明显。

数据量太大不适合二分查找

 二分查找底层依赖的是数组,数组需要的是一段连续的存储空间,所以我们的数据比较大时,比如1GB,这时候可能不太适合使用二分查找,因为我们的内存都是离散的,可能电脑没有这么多的内存。

代码模板

中间值计算

 二分查找的代码实现起来比较简单,需要说明的地方是中间值的计算,中间值得计算有两种方式,

  • 方式一:int mid = (low +high) >> 1

  • 方式二int mid = low + ((high - low) >> 1)

 方式一存在溢出的风险,当lowhigh比较大时,有可能会导致mid的值错误,从而使程序出错。方式二则可以保证生成的mid一定大于low,小于high

未成功查找的返回值

 循环退出时如果仍然没有查找到 key,那么表示查找失败。可以有两种返回值:

  • -1:以一个错误码表示没有查找到 key
  • l:将 key 插入到 arr 中的正确位置

循环

def binarySearch(arr, l, r, target):
while l <= r: #循环条件
mid = l + ((r - l) >> 1) #获取中间位置,数字的索引(序列前提是有序的)
if arr[mid] == target: #如果查询数字刚好为中间值,返回该值得索引
return mid
elif arr[mid] < target: #如果查询数字比中间数字大,那就去二分后的右边找
l = mid + 1
else: #如果查询数字比中间数字小,那就去二分后的左边找
r = mid - 1
return -1 #如果循环结束,左边大于了右边,代表没有找到


arr = [11, 32, 51, 21, 42, 9, 5, 6, 7, 8]
print(arr)
arr.sort()
print(arr)
while 1:
target = int(input('输入要查找的数:'))
res = binarySearch(arr,0, len(arr) - 1, target)
print(res)
if res == -1:
print('未找到!')
else:
print('找到!')

递归

def binarySearch(arr, l, r, target):
if l <= r:
mid = l + ((r - l) >> 1)
if arr[mid] == target:
return mid
elif arr[mid] < target:
l = mid + 1
else:
r = mid - 1
else:
return -1

arr = [11, 32, 51, 21, 42, 9, 5, 6, 7, 8]
print(arr)
arr.sort()
print(arr)
while 1:
target = int(input('输入要查找的数:'))
res = binarySearch(arr,0, len(arr) - 1, target)
print(res)
if res == -1:
print('未找到!')
else:
print('找到!')

变形

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

 比如我们给定数组1,2,3,4,4,4,5,6,7,7,8,9,我们需要查找第一个等于4的元素。

def binarySearch(arr, l, r, target):
while l <= r:
mid = l + ((r - l) >> 1)
if arr[mid] < target:
l = mid + 1
elif arr[mid] > target:
r = mid - 1
else:
#判断当前是第一个元素或者前一个元素不等于要查找的值,则返回下标,如果前一个元素也等于要查找的值,则继续往前查找。
if mid == 0 or arr[mid - 1] != target:
return mid
else:
r = mid - 1
return -1

arr = [1,2,3,4,4,4,5]
print(arr)
arr.sort()
print(arr)
while 1:
target = int(input('输入要查找的第一个数:'))
res = binarySearch(arr,0, len(arr) - 1, target)
print(res)
if res == -1:
print('未找到!')
else:
print('找到!')
  • 其他的都差不多,主要的区别是在nums[mid]==value时候,因为我们要查找的是第一个等于给定值的元素,所以我们需要判断mid的前一个元素等不等于给定值,如果前一个元素也等于给定值,则需要继续往左边查找。
  • 查找最后一个等于给定值的元素,判断mid == len(arr) - 1 or arr[mid + 1] != target是否满足,满足返回mid,否则 l = mid + 1

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

 比如我们给定数组1,2,3,4,4,4,5,6,7,7,8,9,15,26,34,45,我们随便输入一个值,这个值可以是数组里面的值,也不可不在数组里面,查找出第一个比给定值大的元素。

def binarySearch(arr, l, r, target):
while l <= r:
mid = l + ((r - l) >> 1)
if arr[mid] > target:
#判断当前是第一个元素或者前一个元素不等于要查找的值,则返回下标,如果前一个元素也等于要查找的值,则继续往前查找。
if mid == 0 or arr[mid - 1] <= target: return mid
else: r = mid - 1
else:
l = mid + 1
return -1

arr = [1,2,3,4,4,4,5,6,7,7,8,9,15,26,34,45]
print(arr)
arr.sort()
print(arr)
while 1:
target = int(input('查找第一个大于输入的数:'))
res = binarySearch(arr, 0, len(arr) - 1, target)
print(res)
if res == -1:
print('未找到!')
else:
print('找到!')
  • 我们需要判断当nums[mid] > value时,nums[mid-1]是否小于或者等于给定值,如果是则mid就是第一个大于给定值的元素,如果不是这继续往左边查找。
  • 查找最后一个大于给定值的元素,直接返回数组最后一个元素就好了。

69-x的平方根

题目

  • 难度:简单

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

  • 示例:

    输入: 4
    输出: 2

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

题解

#二分查找
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
l = 0 #下界
r = x #上界
ans = -1 #返回结果初始化为-1

while l <= r:
mid = l + ((r - l) >> 1)
if mid * mid <= x: #x的平方根的整数部分ans满足mid * mid <= x的最大mid值
ans = mid
l = mid + 1 #满足mid * mid <= x的最大mid值,右移寻找最大mid值
else:
r = mid - 1
return ans
  • 时间复杂度:O(logn),即为二分查找需要的次数。

  • 空间复杂度:O(1)

  • 思路

    • 首先随便猜一个近似值 x,然后不断令 x 等于 x和 a/x 的平均数,迭代个六七次后 x 的值就已经相当精确了。
    • 每一次迭代后,我们都会距离零点更进一步,所以当相邻两次迭代得到的交点非常接近时,我们就可以断定,此时的结果已经足够我们得到答案了。一般来说,可以判断相邻两次迭代的结果的差值是否小于一个极小的非负数 ϵ,其中ϵ 一般可以取 10610^{-6}10710^{-7}
  • 原理:不断用(x,f(x))(x,f(x))的切线来逼近方程x2a=0x^2-a=0的根。a\sqrt{a}实际上就是x2a=0x^2-a=0的一个正实根,这个函数的导数是2x2x。也就是说,函数上任意一点(x,f(x))(x,f(x))处的切线斜率是2x2x。那么,xf(x)/2xx-f(x)/2x就是一个比xx更接近的近似值。代入f(x)=x2af(x)=x^2-a得到x(x2a)/(2x)x-(x^2-a)/(2x),也就是(xa/x)/2(x-a/x)/2。同样的方法可以用在其它的近似值计算中。

  • Qxf(x)/(2x)x-f(x)/(2x)怎么得到的?

牛顿法

#牛顿法
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x == 0:
return 0
a, x0 = float(x), float(x)
while True:
xi = 0.5 * (x0 + a / x0)
if abs(x0 - xi) < 1e-7:
break
x0 = xi
return int(x0)
  • 时间复杂度:O(logn),此方法是二次收敛的,相较于二分查找更快。
  • 空间复杂度:O(1)

744-寻找比目标字母大的最小字母

题目

  • 难度:简单

  • 题目:给你一个排序后的字符列表 letters ,列表中只包含小写英文字母。另给出一个目标字母 target,请你寻找在这一有序列表里比目标字母大的最小字母。

    在比较时,字母是依序循环出现的。举个例子:

    • 如果目标字母 target = 'z' 并且字符列表为 letters = ['a', 'b'],则答案返回 'a'
  • 示例:

    输入:
    letters = ["c", "f", "j"]
    target = "a"
    输出: "c"

    输入:
    letters = ["c", "f", "j"]
    target = "c"
    输出: "f"

    输入:
    letters = ["c", "f", "j"]
    target = "d"
    输出: "f"

    输入:
    letters = ["c", "f", "j"]
    target = "g"
    输出: "j"

    输入:
    letters = ["c", "f", "j"]
    target = "j"
    输出: "c"

    输入:
    letters = ["c", "f", "j"]
    target = "k"
    输出: "c"
  • 提示:

    • letters长度范围在[2, 10000]区间内。
    • letters 仅由小写字母组成,最少包含两个不同的字母。
    • 目标字母target 是一个小写字母。

题解

  • 思路:类似查找第一个大于给定值的元素,不同之处是:
    1. 返回的不是下标,是元素
    2. 不需要判断所求元素的位置,换句话说,假设数组中重复字母为所求,我们不需要关注重复数组的第几个元素是我们需要的,因为都满足题意,直接返回就行了,所以不需要判断是否满足mid == 0 or letters[mid - 1] != target
    3. 若查找不到,返回的不是-1,而是数组第一个值,即letters[0]
class Solution(object):
def nextGreatestLetter(self, letters, target):
"""
:type letters: List[str]
:type target: str
:rtype: str
"""
l = 0
r = len(letters) - 1
ans = letters[0] #初始化返回结果ans = letters[0]
while l <= r:
mid = l + ((r - l) >> 1)
if letters[mid] > target: #若letters[mid] > target,符合题目要求
ans = letters[mid] #将letters[mid]复制给ans
r = mid - 1 #查找满足letters[mid] > target的最小值
else:
l = mid + 1
return ans
  • 时间复杂度:O(logn)
  • 空间复杂度:O(1)

540-有序数组中的单一元素

题目

  • 难度:中等

  • 题目:给定一个只包含整数的有序数组,每个元素都会出现两次,唯有一个数只会出现一次,找出这个数。

  • 示例:

    输入: [1,1,2,3,3,4,4,8,8]
    输出: 2

    输入: [3,3,7,7,10,11,11]
    输出: 10
  • 注意:您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

题解

  • 有序数组 + 时间复杂度O(logn) +空间复杂度O(1),就要联想到二分查找~
  • 分析:
    • 每个元素都会出现两次,唯有一个数只会出现一次。因此,数组的长度是奇数,单个的数字只会出现在下标为偶数的位置。
    • 因此可以延伸出以下两种思路:
      1. 满足题意下,数组长度是奇数即存在单个数字。根据数组的长度去判断每次查找的区间:计算mid,判断nums[mid]前面或者后面是否有重复的数字,假设nums[mid]前面的数字与nums[mid]相等,看nums[0:mid-2]和nums[mid+1:]两个区间的长度,下一次移动的方向就往区间长度是奇数的方向移动。如果nums[mid]前面和后面的数字都与nums[mid]不等,说明nums[mid]即为所求。直到l和r指向同一个数,那么这个数即为所求。
      2. 满足题意下,单个出现数字的下标是偶数。对偶数索引做二分查找,计算mid,保证mid每次都是偶数,判断nums[mid]和后一个数是否相等,如果相等,nums[mid]就不是单一元素,且单个元素在nums[mid]之后;如果不相等,单个元素则可能就说nums[mid]或在nums[mid]之前。当l==r,搜索空间剩一个元素,那即为所求。
  • 个人认为思路1在面试时候会更好解释
#思路1
class Solution(object):
def singleNonDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l = 0
r = len(nums) - 1
while l < r:
mid = l + ((r - l) >> 1)
if nums[mid] == nums[mid - 1]: #判断nums[mid]与前一个数是否相等
if (mid - 1) % 2 == 0: #判断mid左侧区间长度
l = mid + 1
else:
r = mid - 2
elif nums[mid] == nums[mid + 1]: #判断nums[mid]与后一个数是否相等
if mid % 2 == 0: #判断mid左侧区间长度
l = mid + 2
else:
r = mid - 1
else:
return nums[mid]
return nums[l]
  • 时间复杂度:O(logn)
  • 空间复杂度:O(1)
#思路2
class Solution(object):
def singleNonDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""

l = 0
r = len(nums) - 1
while l < r:
mid = l + (r - l) // 2
if mid % 2 == 1: #保证mid始终是偶数
mid -= 1
if nums[mid] == nums[mid + 1]: #如果nums[mid]==nums[mid+1],单个数在nums[mid]右侧
l = mid + 2
else:
r = mid #否则,单个数是nums[mid]或nums[mid]左侧
return nums[l] #l == r时找到
  • 时间复杂度:O(log(n/2)) = O(logn)
  • 空间复杂度:O(1)

278-第一个错误的版本

题目

  • 难度:简单

  • 题目:你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。

    假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本。

    你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

  • 示例:

    给定 n = 5,并且 version = 4 是第一个错误的版本。

    调用 isBadVersion(3) -> false
    调用 isBadVersion(5) -> true
    调用 isBadVersion(4) -> true

    所以,4 是第一个错误的版本。

题解

  • 分析:版本号n取值范围[1,2,...,n],找到第一个出错的版本。第一个出错版本的特点是,其前一个版本为false,自身显示为true

  • 思路:

    • 计算mid
    • 判断mid是否为true,如果是true,判断mid-1是否为false,如果是false,返回mid,如果mid-1true,说明第一个错误版本在mid左侧。
    • 如果midfalse,判断mid+1是否为true,如果是true,返回mid+1,如果mid + 1false,说明第一个错误版本在mid右侧。
  • 语法知识点:Python中is==的区别

    • https://juejin.im/entry/5a3b62446fb9a0451f311b5c
    • 在ython中一切都是对象
    • Python中对象包含的三个基本要素,分别是:id(身份标识)、type(数据类型)和value(值)。对象之间比较是否相等可以用==,也可以用is。
    • is和==都是对对象进行比较判断作用的,但对对象比较判断的内容并不相同。(is是内存地址,==是值)
      • is比较的是两个对象的id值是否相等,也就是比较两个对象是否为同一个实例对象,是否指向同一个内存地址。
      • ==比较的是两个对象的内容是否相等,默认会调用对象的__eq__()方法。
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):

class Solution(object):
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
l = 1
r = n
while l <= r:
mid = l + (r - l) // 2
if isBadVersion(mid) is True:
if isBadVersion(mid - 1) is False:
return mid
else:
r = mid - 1
else:
if isBadVersion(mid + 1) is True:
return mid + 1
else:
l = mid + 1
return None
  • 时间复杂度:O(logn)
  • 空间复杂度:O(1)

153. 寻找旋转排序数组中的最小值

题目

  • 难度:中等

  • 题目:假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

    请找出其中最小的元素。你可以假设数组中不存在重复元素。

  • 示例:

    输入: [3,4,5,1,2]
    输出: 1

    输入: [4,5,6,7,0,1,2]
    输出: 0

题解

  • 分析:升序排序数组,旋转,从旋转点可以将数组切分为左右两部分,左右部分依旧是升序。因此,可以转化为寻找旋转点,旋转点下一个数就是最小值。
    • 旋转点特点
      • 旋转点左侧元素 > 数组第一个元素
      • 旋转点右侧元素 <数组第一个元素
    • 两种情况
      • 最小值在数组中:数组的第一个元素会大于数组的最后一个元素
      • 最小值在数组头:数组的第一个元素会小于数组的最后一个元素
    • 区间判断
      • 计算mid
      • 如果nums[mid] > 数组第一个元素,说明最小值在mid右侧
      • 如果nums[mid] < 数组第一个元素,说明最小值在mid左侧
    • 确定最小值:找到旋转点后下一个数就是最小值。
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l = 0
r = len(nums) - 1
if nums[r] > nums[l] or len(nums) == 1: #未旋转或数组长度等于1时,返回数组第一个数字
return nums[0]
while l <= r:
mid = l + (r - l) // 2
if nums[mid] > nums[mid + 1]: #nums[mid]是旋转点,返回下一个元素
return nums[mid + 1]
if nums[mid - 1] > nums[mid]: #nums[mid - 1]是旋转点,返回下一个元素
return nums[mid]
if nums[mid] > nums[0]: #nums[mid]大于数组第一个元素,最小值在mid右侧
l = mid + 1
else: #否则在mid左侧
r = mid - 1
  • 时间复杂度:O(logn)
  • 空间复杂度:O(1)

34-在排序数组中查找元素的第一个和最后一个位置

题目

  • 难度:中等

  • 题目:给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

    你的算法时间复杂度必须是 O(log n) 级别。如果数组中不存在目标值,返回 [-1, -1]。

  • 示例:

    输入: nums = [5,7,7,8,8,10], target = 8
    输出: [3,4]

    输入: nums = [5,7,7,8,8,10], target = 6
    输出: [-1,-1]

题解

  • 分析:本题和查找第一个等于给定值的元素思路一样。
  • 思路:
    • 初始化list保存返回结果
    • 先查找第一个等于给定值的元素,将下标加入list
    • 再查找最后一个等于给定值的元素,将下标加入list
  • 算法:
    • 计算mid
    • 如果nums[mid] > target,说明在mid左侧
    • 如果nums[mid] < target,说明在mid右侧
    • 如果nums[mid] == target,判断当前是第一个元素或者前一个元素不等于要查找的值,则将下标加入list,如果前一个元素也等于要查找的值,则r = mid - 1
    • 如果nums[mid] == target,判断当前是最后一个元素或后一个元素不等于要查找的值,则将下标加入list,否则l = mid + 1
class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
res = []
res.append(self.firstNum(nums,target))
res.append(self.lastNum(nums,target))
return res
def firstNum(self, nums, target): #查找第一个元素
l = 0
r = len(nums) - 1
while l <= r:
mid = l + (r - l) // 2
if nums[mid] < target:
l = mid + 1
if nums[mid] > target:
r = mid - 1
if nums[mid] == target:
if mid == 0 or nums[mid] != nums[mid - 1]:
return mid
else:
r = mid - 1
return -1
def lastNum(self, nums, target): #查找最后一个元素
l = 0
r = len(nums) - 1
while l <= r:
mid = l + (r - l) // 2
if nums[mid] < target:
l = mid + 1
if nums[mid] > target:
r = mid - 1
if nums[mid] == target:
if mid == len(nums) - 1 or nums[mid] != nums[mid + 1]:
return mid
else:
l = mid + 1
return -1
  • 时间复杂度:O(logn)
  • 空间复杂度:O(1)
文章作者: Lesy
文章链接: https://lesylin.com/2020/06/29/leetcode-%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/
文章声明: 转载请注明文章链接
打赏
  • 微信
  • 支付宝

Comment