Skip to content

Latest commit

 

History

History
388 lines (277 loc) · 11.5 KB

二分查找.md

File metadata and controls

388 lines (277 loc) · 11.5 KB
Raw

二分查找

1.经典二分算法

给定排序数组nums，搜索某个数的索引。

需要定义搜索区间的形式，是左闭右开、两边闭。区间的开闭还决定了区间的初始条件、循环的终止条件是否需要带等号以及新的搜索区间的生成。

例：nums = [0,2,3,5,7,9,12,13,14]，target=14

两边闭的区间：

init:
	初始搜索区间为：[0, 8]
loop1:
	搜索范围为：[0, 8]
    中间索引为：mid = 4, nums[4] = 7
    判断下一次搜索范围： 7 < 14, 往右边搜索 l = 4 + 1 = 5
loop2:
	搜索范围为：[5, 8]
	中间索引为：mid = 6, nums[6] = 12
	判断下一次搜索范围：12 < 14, 往右边搜索 l = 6 + 1 = 7
loop3:
	搜索范围为: [7, 8]
	中间索引为：mid = 7, nums[7] = 13
	判断下一次搜索范围： 13 < 14，往右边搜索 l = 7 + 1 = 8
lopp4:
	搜索范围为：[8, 8]
	中间索引为：mid = 8, nums[8] = 14
	当前mid所在的位置数值等于搜索的值，直接返回mid

  1. 初始搜索区间：初始的搜索区间为[0, n-1]

  2. 生成新的搜索区间：两边闭区间每次循环判断nums[mid] == target之后，若不相等，新的搜索区间会将mid的左右两个数作为新的端点，这是因为mid已经搜索过了，所以不需要把mid包含在新的搜索空间中；而且如果不加减1，会出现bug，考虑搜索范围：[a, a+1]，mid=a，如果搜索目标在a+1的位置，下一次搜索范围仍是l = a, r = a+1的话就会陷入死循环，因此需要使用mid右边的一个点作为新的端点,[a+1, a+1]，最后得到结果，并且没有死循环。

  3. 循环终止条件：循环的终止条件是当左端点比右端点大时，如：[a+1, a]就不是一个合法的两边闭的区间，就终止循环，while的条件写作：l <= r，等号不能去，去掉之后对于只有一个元素的区间[a, a]还没搜索就退出，返回了-1

(计算mid时，采用l + (r - l) //2而不使用(l + r) // 2是防止整数溢出，当然python不用害怕这点)

def search(nums, target):
    # 初始搜索区间
    l, r = 0, len(nums)-1
    # 终止条件
    while l <= r:
        mid = l + (r - l) // 2
        if target == nums[mid]:
            return mid
        elif nums[mid] > target:
            # 生成新的搜索区间
            r = mid-1
        else:
            l = mid+1
    return -1

左闭右开区间：

例：nums = [0,2,3,5,7,9,12,13,14]，target=5

init:
	初始化搜索区间为：[0, 9)
loop1:
	搜索区间为：[0, 9)
	中间索引为：mid = 4, nums[mid] = 7
	判断下一次搜索区间, 5 < 7，往左边搜索：r = 4
loop2:
	搜索区间为：[0, 4)
	中间索引为：mid = 2, nums[mid] = 3
	判断下一次搜索区间, 5 > 3，往右边搜索：l = 3
lopp3:
	搜索区间为：[3, 4)
	中间索引为：mid = 3, nums[mid] = 5
	当前mid所在的位置数值等于搜索的值，直接返回mid

左闭右开区间的判断条件与两边闭的区间有三处不同：

  1. 初始条件：[0, 9)，即右端点为n而不是n-1

  2. 循环终止条件：l < r即可，因为区间[a, a+1)只包含nums[a]这个数，因此不用和上面一样取等号了，加上等号判断区间时，[a, a)反而不是一个合法区间了

  3. 生成新的搜索区间：闭合的端点处在上一次循环中已经判断过了，因此需要用上一次循环mid的左右两边的索引做端点；而开区间不需要加减1，因为本身开区间端点处就没有包含这个端点。

def search(nums, target):
    l, r = 0, len(nums)
    while l < r:
        mid = l + (r - l) // 2
        if target == nums[mid]:
            return mid
        elif nums[mid] > target:
            r = mid
        else:
            l = mid+1
    return -1

2.寻找左右边界的二分搜索

给定升序数组：[1, 2, 2, 2, 3]，target=2，求target在数组中的左边界。

上面的原始二分搜索就无法求出想要的结果，它会在第一个循环时就结束，返回中间索引2，因为第一次循环就判断出中间的数满足target=2，但是并不满足题目要求。当target不存在于数组中时，返回的是数组中小于target的元素个数。

修改一下上面的二分查找，当nums[mid]=target时，说明左边界还在区间的左边；否则还是和前面一样做处理

init:
	初始化搜索区间为：[0, 4]
loop1:
	搜索区间为：[0, 4]
	中间索引为：mid = 2， nums[2] = 2
	判断下一次搜索区间，2 = 2，说明边界还在数组左侧，往左搜索：r = 2-1 = 1
loop2:
	搜索区间为：[0, 1]
	中间索引为：mid = 0, nums[0] = 1
	判断下一次搜索区间，1 < 2，说明边界在右半部分，往右搜索：l = 0+1 = 1
loop3:
	搜索区间为：[1, 1]
	中间索引为：mid = 1, nums[1] = 2
	此时2 = 2，满足条件，但是还是要继续循环，往左搜索：r = 1-1 = 0
此时l = 1, r = 0,不满足条件，退出循环，并且l所指向的索引就是左边界，但是r不是右边界

算法基本上与上面一致，但是当发现nums[mid]=target时我们并不急着返回结果，而是继续尝试搜索左边界，直到退出循环。

def search_boundary(nums, target):
    l, r = 0, len(nums)-1
    while l <= r:
        mid = l + (r - l) // 2
        # 判断条件可以进一步优化，将if和else分支合并到一起
        if nums[mid] == target:
            r = mid - 1
        elif nums[mid] < target:
            l = mid + 1
        else:
            r = mid -1
    return l

当使用两边闭合的区间时，只能使用左指针作为返回值，因为其循环终止条件为：l <= r，退出循环的条件是l 和 r不相等，因此只能用l作为左边界。而使用左闭右开的区间时，就不用考虑这一点。

def search_boundary(nums, target):
    l, r = 0, len(nums)
    while l < r:
        mid = l + (r - l) // 2
        if nums[mid] < target:
            l = mid + 1
        else:
            r = mid
    return l

当target不存在于数组中时要想返回-1，可以在最后判断：

return l if nums[l] == target else -1

寻找右侧边界同理，当发现target=nums[mid]时， 右侧边界肯定还在右边，因此设置l = mid+1

init:
	初始搜索区间为：[0, 4]
lopp1:
	搜索区间：[0, 4]
	中间索引为：mid = 2, nums[2]=2
	判断下一次循环搜索区间：2 = 2,往右搜索：l = 2+1 = 3
loop2:
	搜索区间：[3, 4]
	中间索引为：mid = 3, nums[3]=2
	判断下一次循环搜索区间：2 = 2，往右搜索：l = 3+1 = 4
loop3:
	搜索区间：[4, 4]
	中间索引为：mid = 4, nums[4]=3
	判断下一次循环搜索区间：2 < 3，往左搜索：r = mid-1
此时l > r，并且r指向右边界

def search_boundary_right(nums, target):
    l, r = 0, len(nums)-1
    while l <= r:
        mid = l + (r - l) // 2
        if nums[mid] == target:
            l = mid + 1
        elif nums[mid] < target:
            l = mid + 1
        else:
            r = mid -1
    return l


def search_boundary_right_(nums, target):
    l, r = 0, len(nums)
    while l < r:
        mid = l + (r - l) // 2
        if nums[mid] == target:
            l = mid + 1
        elif nums[mid] < target:
            l = mid + 1
        else:
            r = mid
    return l

同理，如果想在target不在数组中时，返回-1，可以：

return l if l < len(nums) else -1

3.搜索旋转数组

一个升序的有序数组，在某个点处经过旋转得到新的数组，然后在数组中搜索某个值的索引。

例：nums = [4, 5, 6, 0 , 1, 2, 3], target = 2

思路还是二分查找法，但是判断一个数在不在这个搜索区间内，只有当数组是有序的时候才容易判断，所以首先将一个旋转数组分成两半，肯定是一部分有序，另一部分无序，然后先判断哪边是有序的，哪边是无序的，如果是左边数组有序，然后判断target是不是在左边，否则就是在右边；如果是右边有序，先判断是不是在右边，否则就在左边。

def search_rotate(nums, target):
    if len(nums) == 0:
        return -1

    l, r = 0, len(nums) - 1
    while l <= r:
        mid = l + (r - l) // 2
        if nums[mid] == target:
            return mid
        if nums[0] <= nums[mid]:
            if nums[0] <= target < nums[mid]:
                r = mid-1
            else:
                l = mid+1
        else:
            if nums[mid] < target <= nums[-1]:
                l = mid+1
            else:
                r = mid-1
    return -1

方法：判断哪边有序，然后再看target是否在有序的部分，否则是无序部分

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

5.搜索插入位置

搜索插入位置用左闭右开区间比较方便，因为左右指针都指向对应的位置，并且统一。

def searchInsert(self, nums: List[int], target: int) -> int:
    l, r = 0, len(nums)
    while l < r:
        mid = l + (r - l) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            l = mid + 1
        else:
            r = mid
    return l

6.寻找峰值

def findPeakElement(nums):
    l, r = 0, len(nums)-1
    while l < r:
        mid = l + (r - l)//2
        if nums[mid] > nums[mid+1]:
            r = mid
        if nums[mid] < nums[mid+1]:
            l = mid+1
    return l

7.有序数组中的单一元素

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

示例 1:

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

输入: [3,3,7,7,10,11,11] 输出: 10

这题隐藏的信息是：出现一次的元素，左边的数字是成对出现的，因此其索引都是(偶数、奇数)成对出现，右边的元素则是(奇数、偶数)成对出现，如果发现mid左右的数字与mid所在的数字都不一样，那么返回nums[mid]，否则在mid左右判断：如果成对出现的数字的索引是奇数在前，说明当前在单一元素的右边，搜索区间就往左跑，否则往右跑。

def search(nums):
    # 注意这里初始化右边界为len(nums)-1，循环判断mid+1时数组越界
    l, r = 0, len(nums) - 1
    while l < r:
        mid = l + (r - l) // 2
        if nums[mid - 1] != nums[mid] and nums[mid] != nums[mid + 1]:
            return nums[mid]
        elif nums[mid - 1] == nums[mid]:
            if (mid - 1) % 2 == 0:
                l = mid + 1
            else:
                r = mid
        elif nums[mid] == nums[mid+1]:
            if mid % 2 == 0:
                l = mid + 1
            else:
                r = mid
   return nums[l]

8.找到k个最接近的元素

相关题目

4.寻找两个有序数组的中位数

33.搜索旋转排序数组

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

35.搜索插入位置

69.X的平方根

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

162.寻找峰值

278.第一个错误版本

374.猜数字大小

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

658.找到k个最接近的元素

704.二分查找

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