欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

在有序旋转数组中找到最小值

程序员文章站 2024-03-15 20:29:00
...
/**
 * Created by lxw, [email protected] on 2017/11/5.
 * 给定一个可能旋转过的有序数组arr,可能存在重复的值,返回arr中的最小值
 */
public class rotatedArrayMin {

    public int getMin(int[] arr){
        int low = 0;
        int high = arr.length - 1;
        int mid = 0;
        while (low < high){
            if(low == high - 1){
                break;
            }
            if(arr[low] < arr[high]){
                return arr[low];
            }
            mid = (low + high) / 2;
            if(arr[low] > arr[mid]){
                high = mid;
                continue;
            }
            if(arr[mid] > arr[high]){
                low  =mid;
                continue;
            }
            while (low < mid){
                if(arr[low] == arr[mid]){
                    low++;
                } else if(arr[low] < arr[mid]){
                    return arr[low];
                } else {
                    high = mid;
                    break;
                }
            }
        }
        return Math.min(arr[low], arr[high]);
    }

    public static void main(String[] args){
        rotatedArrayMin tmp = new rotatedArrayMin();
        int[] arr = {6, 7, 1, 2, 3, 4, 5, 6};
        System.out.println(tmp.getMin(arr));
    }
}