catalogue

Title:

Idea:  

code:  

result:  

Title:

Moving the first elements of an array to the end of the array is called array rotation. Enter a rotation of an incrementally sorted array and output the smallest element of the rotation array. For example, arrays   [3,4,5,1,2] is a rotation of [1,2,3,4,5], and the minimum value of the array is 1.   

Example 1:

Input: [3,4,5,1,2]
Output: 1
Example 2:

Input: [2,2,2,0,1]
Output: 0

Source: LeetCode
Link: https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof

Idea:  

Analysis:
1. Normally, the front array is incremented and the rear array is incremented
  For ordered arrays, we can quickly find the results by binary search
  Details:
  (1) When the search value is less than the previous value, we will find it. However, note that because the subscript mid-1 is used, we should ensure mid= 0
  (2) Next, we need to find a way to cut off a part of the range that cannot contain the result.
      Through analysis, we know that the preceding arrays are all greater than or equal to numbers[0], and the following arrays are all less than or equal to numbers[0]
  (3) Therefore, when the value pointed to by mid is greater than numbers[0], we can determine that mid is in the previous array, so begin=mid+1;
  (4) When the value pointed to by mid is less than numbers[0], we can determine that mid is in the following array, so end=mid-1;
  (5) When equal, if numbers[mid] is not equal to the last number at the same time, that is {5,5,5,0,1}, we can conclude that mid is in front
              If numbers[mid] is equal to the last number at the same time, we can only traverse and search for the minimum value
 2. After the main code part is written, you must remember to analyze special cases, such as {1,2,3,4} incremental array, because it does not contain the results we want (the latter is smaller than the former)
      Therefore, this situation will go to the end of the cycle, so finally return numbers[0]
3. Finally, consider the case of numbers=null and the case of length 0. return -1 will do.

code:  

package JianZhiOffer;

public class Offer11 {
    public static void main(String[] args) {
        Solution11 solution11=new Solution11();
        System.out.println(solution11.minArray(new int[]{5,5,5,1,5}));
    }
}
/*
Analysis:
1.Normally, the front array is incremented and the rear array is incremented
  For ordered arrays, we can quickly find the results by binary search
  Details:
  (1)When the search value is less than the previous value, we will find it. However, note that because the subscript mid-1 is used, we should ensure mid= 0
  (2)Next, we need to find a way to cut off a part of the range that cannot contain the result.
      Through analysis, we know that the preceding arrays are all greater than or equal to numbers[0], and the following arrays are all less than or equal to numbers[0]
  (3)Therefore, when the value pointed to by mid is greater than numbers[0], we can determine that mid is in the previous array, so begin=mid+1;
  (4)When the value pointed to by mid is less than numbers[0], we can determine that mid is in the following array, so end=mid-1;
  (5)When equal, if numbers[mid] is not equal to the last number at the same time, that is {5,5,5,0,1}, we can conclude that mid is in front
              If numbers[mid] is equal to the last number at the same time, we can only traverse and search for the minimum value
  (6)After the main code part is written, we must remember to analyze special cases, such as {1,2,3,4} incremental array, because it does not contain the results we want (the latter is smaller than the previous)
      Therefore, this situation will go to the end of the cycle, so finally return numbers[0]
  (7)Finally, consider the case of numbers=null and the case of length 0. return -1 will do.
 */
class Solution11 {
    public int minArray(int[] numbers) {
        if(numbers==null){
            return -1;
        }
        int length=numbers.length;
        if(length==0){
            return -1;
        }
        int begin=0;
        int end=length-1;
        int mid;
        while(begin<=end){
            mid=(begin+end)/2;
            //System.out.println(mid);
            if(mid!=0&&numbers[mid]<numbers[mid-1]){
                return numbers[mid];
            }else if(numbers[mid]<numbers[0]){
                end=mid-1;
            }else if(numbers[mid]>numbers[0]){
                begin=mid+1;
            }else{
                if(numbers[mid]==numbers[end]){
                    return search(numbers,begin,end);
                }else{
                    begin=mid+1;
                }
            }
        }
        return numbers[0];
    }
    public static int search(int[] numbers,int begin,int end){
        int result=numbers[begin];
        for(int i=0;i<end;i++){
            if(result>numbers[i]){
                result=numbers[i];
            }
        }
        return result;
    }
}

result: