单身狗🐕言论：你单身，我单身，我们早晚在一起

小惡魔😈言論：今天你倆分了沒？

好了，言归正传，本文是关于面试经典 150 题中二分查找题目的汇总

二分查找

二分查找（Binary Search），也叫折半查找，是一种常见的查找算法，适用于有序的元素集合中查找特定元素的问题。它的基本思路是，将待查找的元素与有序集合的中间元素进行比较，如果中间元素大于待查找元素，则在中间元素的左半部分继续查找；如果中间元素小于待查找元素，则在中间元素的右半部分继续查找；如果中间元素恰好等于待查找元素，则直接返回该元素的位置。

二分查找算法的时间复杂度为O(logn)O(log n)O(logn)，其中n是元素的个数。

下面是一个使用迭代实现二分查找的Python代码示例：

def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        # 建议写成 min = left + (right - left) // 2 防止溢出
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

这个函数接受一个升序排列的列表和一个待查找的元素，返回该元素在列表中的位置。首先初始化左右两个指针，分别指向列表的开头和结尾。然后进入循环，每次将左右指针的中间位置作为中间指针，将中间指针指向的元素与目标元素进行比较，根据比较结果更新左右指针的位置。如果中间元素等于目标元素，则直接返回中间指针的位置。如果循环结束时还没有找到目标元素，则返回-1表示查找失败。

需要注意的是，这个算法要求列表是升序排列的，否则无法保证正确性。此外，如果列表中有多个与目标元素相等的元素，该算法只能返回其中的一个位置。如果需要查找所有等于目标元素的位置，则需要进行适当的修改。

二分的原理很简单，但是和二分相关的题目会有很多细节的东西在里边。

35. 搜索插入位置

35. 搜索插入位置 - 力扣（Leetcode）

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

 

提示:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 为 无重复元素 的 升序 排列数组
• -104 <= target <= 104

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

因为是寻找插入位置，所以最后是返回l。

162. 寻找峰值

162. 寻找峰值 - 力扣（Leetcode）

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

 

示例 1：

输入： nums = [1,2,3,1]
输出： 2
解释： 3 是峰值元素，你的函数应该返回其索引 2。

示例 2：

输入： nums = [1,2,1,3,5,6,4]
输出： 1 或 5 
解释： 你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。

 

提示：

• 1 <= nums.length <= 1000
• -231 <= nums[i] <= 231 - 1
• 对于所有有效的 i 都有 nums[i] != nums[i + 1]

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        
        def n(i):
            return float('-inf') if i==-1 or i == len(nums) else nums[i]
        
        l,r = 0,len(nums)-1
        while l<=r:
            m = l + (r-l)//2
            if n(m) < n(m+1):
                l = m+1
            elif n(m) < n(m-1):
                r = m-1
            else:
                return m

这个题的精髓在于使用辅助函数n()简化判断边界问题。

其他的思路就很清晰了，找出局部最大值即可，这段代码如果存在好几个局部最大值，找的应该是偏右的那个。

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

153. 寻找旋转排序数组中的最小值 - 力扣（Leetcode）

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
• 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

 

示例 1：

输入： nums = [3,4,5,1,2]
输出： 1
解释： 原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

输入： nums = [4,5,6,7,0,1,2]
输出： 0
解释： 原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

示例 3：

输入： nums = [11,13,15,17]
输出： 11
解释： 原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

 

提示：

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums 中的所有整数 互不相同
• nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

做题之前我们先想一下：

1 2 3 4 5 6 7    left<mid mid<right   min [left:mid]
2 3 4 5 6 7 1    left<mid mid>right   min [mid:right]
3 4 5 6 7 1 2    left<mid mid>right   min [mid:right]
4 5 6 7 1 2 3    left<mid mid>right   min [mid:right]
5 6 7 1 2 3 4    left>mid mid<right   min [left:mid] [mid:right]
6 7 1 2 3 4 5    left>mid mid<right   min [left:mid] 
7 1 2 3 4 5 6    left>mid mid<right   min [left:mid]

找规律就行了：

mid和left比的话，不好弄区间，

mid和right比，是一一对应关系，

所以我们比较就按照mid和right来。

那继续看这个图2，我们可以看到：

• mid > right时候最小值在区间(mid,right]

• mid < right时候最小值在区间[left,mid]

注意这里的开闭区间！！！

逻辑捋清了，可以写代码了。

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

33. 搜索旋转排序数组

33. 搜索旋转排序数组 - 力扣（Leetcode）

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

 

示例 1：

输入： nums = [4,5,6,7,0,1,2], target = 0
输出： 4

示例 2：

输入： nums = [4,5,6,7,0,1,2], target = 3
输出： -1

示例 3：

输入： nums = [1], target = 0
输出： -1

 

提示：

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• nums 中的每个值都 独一无二
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -104 <= target <= 104

这个题要分情况考虑，查找过程中每次将数组一分为二：

• 找到：返回

• 没找到，一分为二

  • 有序区：二分查找

  • 无序区：

    • 找到：返回

    • 没找到：一分为二

      • 有序区：二分查找

      • 无序区……

你们懂我意思没？ 算了。上代码吧。

class Solution:
    def search(self, nums, target: int) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            m = l + (r - l) // 2
            if nums[m] == target:
                return m
            elif nums[l] <= nums[m]:  # 左半边有序
                                      # 注意这里一定要写 <= 
                if nums[l] <= target < nums[m]:
                    r = m - 1
                else:
                    l = m + 1
            else:  # 右半边有序
                if nums[m] < target <= nums[r]:
                    l = m + 1
                else:
                    r = m - 1
        return -1

算法的基本思路是：

1. 初始化搜索范围为整个数组。

2. 用二分查找法找到中间位置 m。

3. 如果 nums[m] 等于目标值，则直接返回 m。

4. 否则，如果左半边有序（即 nums[l] <= nums[m]），判断目标值是否在左半边，如果是则继续在左半边搜索，否则在右半边搜索。

5. 否则，如果右半边有序（即 nums[m] < nums[r]），判断目标值是否在右半边，如果是则继续在右半边搜索，否则在左半边搜索。

6. 如果最终没有找到目标值，则返回 -1。

该算法的关键在于判断左半边和右半边哪一边有序。具体而言，如果 nums[l] <= nums[m]，则左半边一定有序，因为左半边包括了数组的最小值（即旋转点），而最小值是不可能出现在右半边的。如果 nums[m] < nums[r]，则右半边一定有序，因为右半边包括了数组的最大值，而最大值是不可能出现在左半边的。

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

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

 

示例 1：

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

示例 2：

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

示例 3：

输入： nums = [], target = 0
输出： [-1,-1]

 

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums 是一个非递减数组
• -109 <= target <= 109

class Solution:
    def searchRange(self, nums, target):
        l, r = 0, len(nums) - 1
        while l <= r:
            m = l + (r - l) // 2
            if nums[m] >= target:
                r = m - 1
            else:
                l = m + 1
        left = l
        if left >= len(nums) or left<len(nums) and nums[left] != target:
            return [-1, -1]
        r = len(nums) - 1
        while l <= r:
            m = l + (r - l) // 2
            if nums[m] >= target+1:
                r = m - 1
            else:
                l = m + 1
        right = l
        return [left, right - 1]

代码中，首先初始化左右指针 l 和 r，用于指示查找范围。然后，在第一次二分查找中，每次取左右指针的中间值 m，并比较该值与目标值的大小关系，如果中间值大于或等于目标值，则将右指针 r 向左移动到 m-1，否则将左指针 l 向右移动到 m+1。最终，第一次二分查找结束后，左指针 l 就指示了目标值在数组中的起始位置。

接着，如果数组中不存在目标值，则返回 [-1, -1]。否则，第二次二分查找与第一次类似，不同的是在比较时，将目标值加 1，以找到目标值在数组中的结束位置。最终，右指针 r 指示的位置即为目标值在数组中的结束位置。

需要注意的是，由于二分查找的实现方式是左闭右闭区间，所以返回的结束位置应当减去 1。

优化一下：

class Solution:
    def bSearch(self, nums, target):
        l, r = 0, len(nums) - 1
        while l <= r:
            m = l + (r - l) // 2
            if nums[m] >= target:
                r = m - 1
            else:
                l = m + 1
        return l

    def searchRange(self, nums, target):
        left = self.bSearch(nums, target)
        if left >= len(nums) or left < len(nums) and nums[left] != target:
            return [-1, -1]
        right = left + self.bSearch(nums[left:], target+1)
        return [left, right - 1]

由于第二次二分查找是在第一次的基础上进行的，因此第二次的查找范围需要加上第一次查找的起始位置 left。同时，由于二分查找的实现方式是左闭右闭区间，因此返回的结束位置应当减去 1。

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

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

 

示例 1：

输入： nums1 = [1,3], nums2 = [2]
输出： 2.00000
解释： 合并数组 = [1,2,3] ，中位数 2

示例 2：

输入： nums1 = [1,2], nums2 = [3,4]
输出： 2.50000
解释： 合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

这里限制了O(log (m+n))时间复杂度，也就是最多你一层遍历出结果。

最朴素的思想，不考虑空间复杂度，那直接有序合并数组就行：

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        merge = []
        idx1, idx2 = 0, 0
        while idx1 < len(nums1) and idx2 < len(nums2):
            if nums1[idx1] <= nums2[idx2]:
                merge.append(nums1[idx1])
                idx1 += 1
            else:
                merge.append(nums2[idx2])
                idx2 += 1
        if idx1 == len(nums1):
            merge += nums2[idx2:]
        if idx2 == len(nums2):
            merge += nums1[idx1:]
        l = len(merge)
        if l % 2 == 1:
            return float(merge[l // 2])
        else:
            return (merge[l // 2] + merge[l // 2 - 1]) / 2

分析如下：

1. 创建一个空列表 merge，和两个指针 idx1 和 idx2 初始化为 0。

2. 在 while 循环中，比较 nums1 和 nums2 中当前指针所指的元素大小，将较小值加入到 merge 中，并将对应指针加 1。

3. 循环结束后，如果有一个数组的所有元素都已经被遍历完，将另一个数组剩余的元素全部加入到 merge 中。

4. 计算 merge 的长度 l，如果 l 为奇数，则中位数为 merge[l//2]；如果 l 为偶数，则中位数为 (merge[l//2] + merge[l//2-1])/2。

5. 返回中位数。

这段代码的时间复杂度为 O(m+n)O(m+n)O(m+n)，其中 mmm 和 nnn 分别为两个输入数组的长度。因为该算法需要遍历两个数组中的所有元素，并将它们合并成一个新的有序数组，所以时间复杂度是线性的。

空间复杂度为 O(m+n)O(m+n)O(m+n)，因为需要使用一个新的数组 merge 来保存两个输入数组的所有元素，并且在最坏情况下需要同时存储两个输入数组中的所有元素。

74. 搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

• 每行中的整数从左到右按升序排列。
• 每行的第一个整数大于前一行的最后一个整数。

 

示例 1：

输入： matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出： true

示例 2：

输入： matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出： false

 

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

在二维数组中用两次二分，第一次搜索元素在第几行，第二次从该行中寻找元素。

class Solution:
    def biSearch(self, nums, target):
        l, r = 0, len(nums) - 1
        while l <= r:
            m = l + (r - l) // 2
            if nums[m] < target:
                l = m + 1
            elif nums[m] > target:
                r = m - 1
            else:
                return m
        return r

    def searchMatrix(self, matrix, target):
        start = [matrix[i][0] for i in range(len(matrix))]
        i = self.biSearch(start,target)
        '''
        在别的语言里要加这一句，因为可能返回 i = -1
        python中无所谓，因为python中可以取到列表的[-1]
        但是肯定找不到，所以之后的搜索都是没用的，节省时间还是加上的好
        '''
        if i < 0:             
            return False
        j = self.biSearch(matrix[i],target)
        return True if matrix[i][j] == target else False

biSearch 方法的时间复杂度为 O(log⁡n)O(\log n)O(logn)，其中 nnn 是列表 nums 的长度，因为它使用二分查找算法进行搜索。空间复杂度为 O(1)O(1)O(1)，因为它只使用了常数级别的额外空间。

searchMatrix 方法的时间复杂度取决于 biSearch 方法的复杂度和矩阵的大小。具体来说，它需要执行两次二分查找，一次在长度为 mmm 的列表 start 中，一次在长度为 nnn 的列表 matrix[i] 中。因此，它的时间复杂度为 O(log⁡m+log⁡n)=O(log⁡mn)O(\log m + \log n) = O(\log mn)O(logm+logn)=O(logmn)。矩阵的大小为 m×nm \times nm×n，因此空间复杂度为 O(m)O(m)O(m)，因为它需要在内存中存储 start 列表。

用一次二分就行了。

class Solution:
    def biSearch(self, nums, target):
        m, n = len(nums), len(nums[0])
        l, r = 0, m * n - 1
        while l <= r:
            m = l + (r - l) // 2
            i = m // n
            j = m % n
            if nums[i][j] < target:
                l = m + 1
            elif nums[i][j] > target:
                r = m - 1
            else:
                return True
        return False

    def searchMatrix(self, matrix, target):
        return self.biSearch(matrix, target)

biSearch 方法中，首先计算出二维矩阵的行数和列数，然后将矩阵转化为一个长度为 m×nm \times nm×n 的一维数组，其中 mmm 和 nnn 分别为矩阵的行数和列数。接下来使用二分查找算法在这个一维数组上搜索目标元素。

searchMatrix 方法中，直接调用 biSearch 方法进行搜索，如果找到目标元素，则返回 True，否则返回 False。

这段代码的时间复杂度为 O(log⁡(mn))O(\log(mn))O(log(mn))，其中 mmm 和 nnn 分别为二维矩阵的行数和列数。空间复杂度为 O(1)O(1)O(1)，因为只需要常数级别的额外空间来存储一些变量。

需要注意的是，这种方法虽然可以在时间上实现对二维矩阵的二分查找，但是它并没有利用到二维矩阵的特点，对于一些特殊的二维矩阵（比如稀疏矩阵），这种方法可能并不是最优的。