二分查找——旋转数组的最小数字

井底的笨鸟

于 2016-07-22 09:44:22 发布

阅读量788

点赞数

分类专栏：剑指offer 算法/数据结构文章标签：二分查找

本文链接：https://blog.csdn.net/jingsuwen1/article/details/51991837

版权

剑指offer 同时被 2 个专栏收录

42 篇文章

订阅专栏

算法/数据结构

42 篇文章

订阅专栏

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
         if(array == null||array.length == 0)
             return 0;
        int left=0;
        int right=array.length-1;
        if(array[left] == array[right])
            {
            for(int i=1;i<array.length;i++)
                {
                if(array[i] < array[i-1])
                    return array[i];
            }
            return array[left];
        }
        if(array[left] < array[right])
            return array[left];
        //general
        while(left < right-1)
            {
            int mid=left+(right-left)/2;
            if(array[mid] >= array[left])
                left=mid;
            else
                right=mid;
        }
        return array[right];
    }
}