【剑指offer】寻找旋转排序数组中的最小值

发布时间:2017-6-29 10:24:32编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"【剑指offer】寻找旋转排序数组中的最小值",主要涉及到【剑指offer】寻找旋转排序数组中的最小值方面的内容,对于【剑指offer】寻找旋转排序数组中的最小值感兴趣的同学可以参考一下。

描述:

假设一个旋转排序的数组其起始位置是未知的(比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2)。

你需要找到其中最小的元素。

你可以假设数组中不存在重复的元素。

 注意事项

You may assume no duplicate exists in the array.

样例:

给出[4,5,6,7,0,1,2]  返回 0


Java代码:

0,1,2,3,4,5,6,7想象成一个环
只有0开头,7结尾的时候是头小尾大
其他时候都是头大尾小
二分法

public class Solution {
    /**
     * @param nums: a rotated sorted array
     * @return: the minimum number in the array
     */
    public int findMin(int[] nums) {
        // write your code here
    	if(nums == null){
    		return -1;
    	}
    	
    	if(nums.length == 1){
    		return nums[0];
    	}
    	
    	int low = 0;
        int high = nums.length-1;
        
        if(nums[low] < nums[high]){
        	return nums[low];
        }
        
        while(nums[low] > nums[high]){
        	int mid = low + (high-low)/2; 

        	if(mid == low){
        		return nums[high];
        	}
        	
        	if(nums[mid]>nums[low]){
        		low = mid;
        	}
        	
        	if(nums[mid]<nums[low]){
        		high = mid;
        	}
        }
        
        return nums[low];
    }
}




上一篇:MySQL优化 select max(addtime) 改为 select *
下一篇:兼容移动端的后台管理框架

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款