leetcode153 寻找旋转排序数组中的最小值 golang-木庄网络博客

本文摘自网络，作者，侵删。

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

解题思路

二分的变形
利用二分查找，如果一个值大于右侧，则我们可以判断右侧一定存在最小数，反之最小数在左侧。
利用这个特点，递归进行迭代进行。

代码实现

func findMin(nums []int) int {
    i,j := 0,len(nums)-1
    for i<j{
        mid := (i+j)/2
        if nums[mid]>nums[j]{
            i = mid+1
        }else{
            j = mid // 注意不能减1
        }
    }
    return nums[i]
}

本文来自：简书

感谢作者：lucasgao

查看原文：leetcode153 寻找旋转排序数组中的最小值 golang

相关阅读 >>