独身狗言辞：你独身，我独身，我们早晚在一起

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

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

二分查找

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

二分查找算法的时刻复杂度为 $O (l o g n)$ ，其间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

算法的基本思路是：

初始化查找规模为整个数组。
用二分查找法找到中心方位 m。
假如 nums[m] 等于方针值，则直接回来 m。
不然，假如左半边有序（即 nums[l] <= nums[m]），判别方针值是否在左半边，假如是则持续在左半边查找，不然在右半边查找。
不然，假如右半边有序（即 nums[m] < nums[r]），判别方针值是否在右半边，假如是则持续在右半边查找，不然在左半边查找。
假如终究没有找到方针值，则回来 -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]。不然，第2次二分查找与第一次相似，不同的是在比较时，将方针值加 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]

由于第2次二分查找是在第一次的基础进步行的，因而第2次的查找规模需求加上第一次查找的开始方位 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

剖析如下：

创建一个空列表 merge，和两个指针 idx1 和 idx2 初始化为 0。
在 while 循环中，比较 nums1 和 nums2 中当时指针所指的元素大小，将较小值加入到 merge 中，并将对应指针加 1。
循环结束后，假如有一个数组的一切元素都现已被遍历完，将另一个数组剩下的元素全部加入到 merge 中。
计算 merge 的长度 l，假如 l 为奇数，则中位数为 merge[l//2]；假如 l 为偶数，则中位数为 (merge[l//2] + merge[l//2-1])/2。
回来中位数。

这段代码的时刻复杂度为 $O (m + n)$ ，其间 $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

在二维数组顶用两次二分，第一次查找元素在第几行，第2次从该行中寻觅元素。

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)$ ，其间 $n$ 是列表 nums 的长度，由于它运用二分查找算法进行查找。空间复杂度为 $O (1)$ ，由于它只运用了常数级其他额定空间。

searchMatrix 办法的时刻复杂度取决于 biSearch 办法的复杂度和矩阵的大小。具体来说，它需求履行两次二分查找，一次在长度为 $m$ 的列表 start 中，一次在长度为 $n$ 的列表 matrix[i] 中。因而，它的时刻复杂度为 $O(log⁡m+log⁡n)=O(log⁡mn)O(\log m + \log n) = O(\log mn)$ 。矩阵的大小为 $\times n$ ，因而空间复杂度为 $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 办法中，首要计算出二维矩阵的行数和列数，然后将矩阵转化为一个长度为 $\times n$ 的一维数组，其间 $m$ 和 $n$ 别离为矩阵的行数和列数。接下来运用二分查找算法在这个一维数组上查找方针元素。

searchMatrix 办法中，直接调用 biSearch 办法进行查找，假如找到方针元素，则回来 True，不然回来 False。

这段代码的时刻复杂度为 $O(log⁡(mn))O(\log(mn))$ ，其间 $m$ 和 $n$ 别离为二维矩阵的行数和列数。空间复杂度为 $O (1)$ ，由于只需求常数级其他额定空间来存储一些变量。

需求留意的是，这种办法尽管能够在时刻上完成对二维矩阵的二分查找，可是它并没有利用到二维矩阵的特色，对于一些特殊的二维矩阵（比方稀少矩阵），这种办法或许并不是最优的。

😈所谓二分：今天你俩分了没？| 二分查找🔍

二分查找

35.查找刺进方位

162. 寻觅峰值

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

33. 查找旋转排序数组

34. 在排序数组中查找元素的第一个和终究一个方位

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

74. 查找二维 矩阵

作者信息

推广

😈所谓二分：今天你俩分了没？| 二分查找🔍

二分查找

35.查找刺进方位

162. 寻觅峰值

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

33. 查找旋转排序数组

34. 在排序数组中查找元素的第一个和终究一个方位

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

74. 查找二维矩阵

相关文章

Flutter NullSafety工程迁移兼容问题解决

如何用python实现文本转语音功能

Python图像处理（一）python_opencv基本使用

AB实验人群定向HTE模型5 – Meta Learner

作者信息

推广