leetcode刷题：二分查找

系列文章目录

前言

上一周结束了算法入门的一些算法题，这周开始难度明显加大，所以现在记录博客安装算法类型记录，大该2-3天记录一次，加上一些注释，以便以后回忆。

一、二分查找

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

给定一个按照升序排列的整数数组 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]

class Solution:
    def __init__(self):
        self.nums = [5,7,7,8,8,10]
        self.target = 6

    def searchRange(self):
        nums = self.nums
        target = self.target
        # 算法部分
        n = len(nums)
        #如果长度为0，直接返回[-1, -1]
        if n == 0:
            return [-1, -1]
		#寻找第一个数
        def firstPostition(nums, target):
            left = 0
            right = n - 1
            while left < right:
                mid = int((left + right) / 2)
                if nums[mid] < target:
                    left = mid + 1
                elif nums[mid] == target:
                    right = mid
                else:
                    right = mid - 1
            if nums[left] == target:
                return left
            else:
                return -1
		#寻找最后一个数
        def lastPostition(nums, target):
            left = 0
            right = n - 1
            while left < right:
                mid = int((left + right + 1) / 2)
                if nums[mid] < target:
                    left = mid + 1
                elif nums[mid] == target:
                    left = mid
                else:
                    right = mid - 1
            return left


        first = firstPostition(nums, target)
        if first == -1:
            return [-1, -1]
        last = lastPostition(nums, target)
        return [first, last]

2.搜索旋转排序数组

给定一个按照升序排列的整数数组 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]

class Solution:
    def __init__(self):
        self.nums = [4, 5, 6, 7, 0, 1, 2]
        self.target = 0

    def search(self):
        nums = self.nums
        target = self.target
        # 算法部分
        if not nums:
            return -1
        left, right = 0, len(nums) - 1
        #mid的左侧或者右侧必然有一次是有序的，通过比较两侧各自的端点找到有序的那一段，判断目标是否在这一段范围中，如果在，丢弃另一端，如果不在，丢弃这一段。重复这个操作知道找到或搜索结束。
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            if nums[0] <= nums[mid]:
                if nums[0] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[len(nums) - 1]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1

3.搜索二维矩阵

编写一个高效的算法来判断 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

class Solution:
    def __init__(self):
        self.matrix = [[1],[3]]
        self.target = 3

    def searchMatrix(self):
        matrix = self.matrix
        target = self.target
        # 算法逻辑
        if target < matrix[0][0] or target > matrix[-1][-1]:
            return False
		#标准的二分查找
        def search(target, nums):
            low = 0
            height = len(nums) - 1
            mid = (height + low) // 2
            while low != height:
                if nums[mid] == target:
                    return mid
                if nums[mid] < target:
                    low = mid + 1
                else:
                    height = mid
                mid = int((low + height) / 2)
            if nums[low] == target:
                return low
            return -1
		#将二维数组的第一列当作一一维数组，找到目标所在行
        low = 0
        height = len(matrix) - 1

        while low != height:
            mid = (low + height) // 2
            if matrix[mid][0] == target:
                return True
            if matrix[mid][0] < target <= matrix[mid][-1]:
            	#找到后将目标和所在数组传入，调用标准的二分查找
                if search(target, matrix[mid]) == -1:
                    return False
                else:
                    return True
            if matrix[mid-1][-1]>=target:
                height=mid
            else:
                low=mid+1
        #我的二分查找是左闭右开，所以单独测试一下最右边
        if search(target,matrix[-1]) !=-1:
            return True
        return False

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

已知一个长度为 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 次得到输入数组。

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        #数组被分为两段，左边恒大于右边，比较中点和右侧端点来决定指针的移动。
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < nums[right]:
                right = mid
            else:
                left = mid + 1
        return nums[left]

5.寻找峰值

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

给你一个整数数组 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。
峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 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。

class Solution:
    def __init__(self):
        self.nums=[1,2,1,3,5,6,4]
    def findPeakElement(self):
        nums=self.nums
        #算法部分
        idx = 0
        for i in range(1, len(nums)):
            if nums[i] > nums[idx]:
                idx = i
        return idx

这道题本来也可以用二分法，但博主没看懂，所以直接for循环找最大值。

总结

之后的算法题可能会经常更新，但是量不会太多，慢慢学习吧。