题目描述

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。

示例 1:

输入:[3,4,5,1,2]
输出:1
示例 2:

输入:[2,2,2,0,1]
输出:0

算法解析

首先还是得知道二分查找的核心思路是什么:

  1. int low = 0;
  2. int high = arrays.length;
  3. while(low <= high){
  4. int mid = (low + high) >>> 1;
  5. if(arrays[mid] < value){
  6. low = mid + 1;
  7. }else if(arrays[mid] > value){
  8. high = mid - 1;
  9. }else{
  10. return mid;
  11. }
  12. }

对于这个算法来说我们需要处理一些特殊的case

  1. 输入的数组没有重复的数字:[3,4,5,1,2]
  2. 输入的数组包含重复的数字:[3,4,5,1,2,2,2]

x与 y分别指向数组的两边,中间位置为m
1.当data[m]的值大于data[y]的值,说明最小值在[m+1, y]之间,这个时候x赋值为m+1;
2.当data[m]的值小于data[y]值,说明最小值在[x, mid]之间,这个时候y赋值为mid;
3.当data[m]的值等于data[y]值,说明最小值在[x, y]之间的位置;

算法实现

  1. class Solution {
  2. public int minArray(int[] numbers) {
  3. if(numbers == null){
  4. return Integer.MAX_VALUE;
  5. }
  6. int low = 0;
  7. int high = numbers.length - 1;
  8. while(low < high){
  9. int mid = (low + high)/2;
  10. if(numbers[mid] > numbers[high]){
  11. low =mid + 1;
  12. }else if(numbers[mid] > numbers[low]){
  13. high = mid;
  14. }else{
  15. high--;
  16. }
  17. }
  18. return numbers[low];
  19. }
  20. }