【Java】牛客_剣指offer(JZ 6)回転配列の最小数値

テーマの出所:https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&&tqId=11159&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
タイトルの説明
1つの配列の最初のいくつかの要素を配列の末尾に運び、配列の回転と呼ぶ.非減算ソート配列の回転を入力し、回転配列の最小要素を出力します.例えば、配列{3,4,5,1,2}は{1,2,3,4,5}の回転であり、この配列の最小値は1である.NOTE:与えられたすべての要素は0より大きく、配列サイズが0の場合は0を返します.
問題解
問題解決の考え方:

まず、これは間違いなく問題を探して、直接暴力的に並べ替えて最小値を見つけることができますが、出題の意思に合わないに違いありません.

は、回転配列の元の配列が非減算ソートであるため、元の配列は昇順であり、数字は繰り返すことができる.

したがって、配列の開始部分を配列の末尾に運ぶと、配列左部分>配列右部分、すなわち最小値が右部分の最初の数

であることがわかる.

配列は秩序と見なすことができるため、二分で検索することができるが、目標値targetがない、すなわち最小値を決定していないことがこの問題の難点であるため、ここではtargetと中間値を比較するのではなく、中間値と最右値を比較する

である.

array[mid] < array[high]の場合、中間値array[mid]が右部分にあることは分かるが、midは必ずしも最小とは限らないので、highは左に移動し、high = midはhighではなく、mid-1がちょうど最小値

であることを避けることに注意する.

midの場合、中間値array[mid] > array[high]が左部分にあることが分かるので、array[mid]は右に移動し、low

.

low = mid + 1が重複する数字に遭遇すると、array[mid] = array[high]は1ビット

左にシフトする.

最後に、highの場合、最小値

である.

コード実装

/**
 *     
 */
public class Solution {
    public int minNumberInRotateArray(int[] array) {
        //     
        if (array == null || array.length == 0) {
            return 0;
        }
        int low = 0;
        int high = array.length - 1;
        //           ，low = high     ，         low = high
        while (low < high) {
            //     mid      mid=(low+high)/2，   oj        
            int mid = low + (high - low) / 2;
            //    array[mid] < array[high]，array[mid]      ，  high  
            if (array[mid] < array[high]) {
                //             ，  high=mid-1，      mid       
                high = mid;
            }
            //    array[mid] > array[high]，array[mid]      ，  low  
            else if (array[mid] > array[high]) {
                low = mid + 1;
            }
            //    array[mid] = array[high]       ，high    
            else {
                high -= 1;
            }
        }
        return array[low];
    }
}