JAVA练习340- 寻找旋转排序数组中的最小值

题目概览已知一个长度为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.length1 n 5000-5000 nums[i] 5000nums中的所有整数互不相同nums原来是一个升序排序的数组并进行了1至n次旋转来源153. 寻找旋转排序数组中的最小值 - 力扣LeetCode解题分析方法二分查找先进行一次二分令中间索引为 mid起始索引为 i结束索引为 j二分之后得到的两个子数组至少有一个时递增的那么当 nums[ i ] nums[ mid ] 且 nums[ mid ] nums[ j ] 时mid 到 j 一定是递增数组那么最小值一定在左边数组或为 nums[mid]当 nums[ i ] nums[ mid ] 且 nums[ mid ] nums[ j ] 时i 到 mid 一定是递增数组那么最小值一定在右边数组当 nums[ i ] nums[ mid ] nums[ j ] 时整个数组就是递增数组最小值就为 num[ i ]当 nums[ i ] nums[ mid ] nums[ j ] 时不可能存在这种情况时间复杂度O(logn)空间复杂度O(1)class Solution { public int findMin(int[] nums) { int n nums.length; int i 0, j n - 1, min nums[0]; while(i j) { int mid (i j) / 2; if (nums[mid] nums[i] nums[mid] nums[j]) { min Math.min(min, nums[mid]); j mid - 1; } else if (nums[mid] nums[i] nums[mid] nums[j]) { i mid 1; } else if (nums[i] nums[mid]) { min Math.min(min, nums[i]); break; } else { min Math.min(min, nums[j]); break; } } return min; } }