LeetCode-算法-二分查找-第16天

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

已知一个长度为 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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

示例 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 次得到输入数组。 具体题目链接

Python

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left,right=0,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]

思路：首先此题和之前33. 搜索旋转排序数组很像，都是会出现两段有序数组，但此题的目的是寻找最小值。 因此我们需要分析，首先我认为有两种种情况发生： 1.旋转len(nums)*n次，即和原数组一样，还是保持升序，因此可得，最小值一定在左边界。 2.普通情况，即出现nums1和nums2两个有序，且nums1全部大于nums2，因此可知最小值一定在nums2左边界。 那如何寻找最小值在哪呐，我们可以采取nums[mid]让与nums[right]来比大小，如果nums[mid]小于nums[right]，则证明还可能存在比nums[mid]还要小的数，但也不能排除nums[mid]是最小的数，因此right=mid。如果nums[mid]>=nums[right]，则证明nums[mid]可能不是最小值，因此直接去寻找left=mid+1。

GO

func findMin(nums []int) int {
    left,right:=0,len(nums)-1
    for mid:=0;left<right;{
        mid=left+(right-left)/2
        if nums[mid]<nums[right]{
            right=mid
        }else{
            left=mid+1
        }
    }
    return nums[left]
}

思路：同python

162. 寻找峰值

峰值元素是指其值大于左右相邻值的元素。 给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。 你可以假设 nums[-1] = nums[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。

具体题目链接

Python

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left,right=0,len(nums)-1
        while left<right:
            mid=left+(right-left)//2
            if nums[mid]>nums[mid+1]:
                right=mid
            else:
                left=mid+1
        return left

思路：看到这题我当时没思路，这是能用二分法做的吗？数组是无序的，哎。看到解析答案才发现，编程难的不是写代码，是思路，是分析。 此题思路是：只要有上升则必然有下降，那么我只需要与右边进行比较，只要nums[mid]>nums[mid+1]那么mid就可能使峰值，那么只需要检验mid的左边即可，如果mid是峰值的话，那么left会一直增加，直到等于right。如果不是峰值，那么rigth就会挪动到新位置。依次类推，最后得到结果。

GO

func findPeakElement(nums []int) int {
    left,right,mid:=0,len(nums)-1,0
    for left<right{
        mid=left+(right-left)/2
        if nums[mid]>nums[mid+1]{
            right=mid
        }else{
            left=mid+1
        }
    }
    return left
}

思路:同python