首页 > 代码库 > 新手算法学习之路----二分法Find Minimum in Rotated Sorted Array
新手算法学习之路----二分法Find Minimum in Rotated Sorted Array
题目：假设一个旋转排序的数组其起始位置是未知的（比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2）。
你需要找到其中最小的元素。
你可以假设数组中不存在重复的元素。
思路：首先排除三种极端情况，空，只有一个元素，以及整个数组都是顺序排列的。
当顺序的数组随机旋转排列后，就分为两个顺序列入题目中的4567和012，寻找到中间数来和数组最后一个元素对比，如果大于的话说明最小的数在中间数的右边，如果小于的话说明最小数在中间数的左边，然 后继续按照二分法来找。注：不会出现中间数等于最后一个元素，因为题目中说明了没有重复元素。
问题：我当时的思路是这两个数组能不能被分成两部分，两个升序数组来求最小数，最后证明不对；由于思维被禁锢在二分法使用的前提是一个排好序的数组，结果更本没有想到使用下边的办法，这个是我借鉴别人的偶，自己又简化了一下。
public int findMin(int[] nums) { // write your code here if( nums == null || nums.length == 0) //先排三种特殊的情况 return 0; if(nums.length == 1) return nums[0]; int low = 0; int high = nums.length -1; int mid = low; while(low < high){ mid = (low + high)/2; if(nums[mid] > nums[high]){ //如果中间大于最后一个元素那说明最小的数在中间数的右边 low = mid + 1; //数组的前一半排除掉 }else if( nums[mid] < nums[high]){ //如果中间数小于最后一个元素，说明中间数后面部分的升序部分里面，那最小说就在中间数左边了 high = mid ; } } return nums[low];
}
新手算法学习之路----二分法Find Minimum in Rotated Sorted Array
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。