LeetCode:寻找旋转排序数组中的最小值【153】
题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [0,1,2,4,5,6,7]
可能变为 [4,5,6,7,0,1,2]
)。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。
示例 1:
输入: [3,4,5,1,2]
输出: 1
示例 2:
输入: [4,5,6,7,0,1,2]
输出: 0
题目分析
一次循环,找最小值就可以找到答案。但是作为一道中等难度的题目,绝对要求不会很低。
从算法角度看,这可以是一道二分搜索的变形,找到的目标值是满足某些特定条件的值,在这里要求如下:
Java题解
public class FindMinInRotatedSortedArray_153 {
public int findMin(int[] nums) {
int left = 0;
int right = nums.length-1;
while (left<right)
{
int mid =left+(right-left)/2;
if(mid>0&&nums[mid]>nums[mid-1])
return nums[mid];
//变换条件
if(nums[left]<nums[mid]&&nums[mid]>nums[right])
left=mid+1;
else
right=mid-1;
}
return nums[left];
}
}