整列配列反転後の検索

タイトル:
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
秩序配列がある点で反転したと仮定し、ターゲット値を検索し、見つかった場合は下付きを返し、そうでなければ-1を返します.重複する数がないと仮定します.
考え方:
まず、秩序配列の最小値の検索を参照してください.http://blog.csdn.net/u012243115/article/details/41923667.
本題では依然として二分法を用いており,targetが前半か後半かをどのように判断するかが難点である.重複しない配列4 5 6 7 0 1 2について、A[begin]<=A[mid]を満たす場合、すなわち配列の最初の値が中間値4<7より小さい場合、前半の配列秩序が断定される.この条件を満たさない場合(例えば、4 5 0 1 2)は、後半の順序を説明する.この配列を真ん中から分けると、少なくとも半分の配列が秩序化されているに違いないからだ.次にtargetが秩序化された半セグメントにあるかどうかを判断し(これはよく判断される)、もしあるならば、秩序化された配列の中で検索することに相当し、簡単である.秩序のある半分でなければ、きっと別の半分にあります.次に反復を使用してtargetを見つけることができます.

public class Solution {  
public int search(int A[], int n, int target)   
    {  
        int begin = 0;  
        int end = n-1;  
        while(begin <= end)  
        {  
            int mid = (begin + end)/2;  
            //  mid   target，   ，    ，    ，   target            
            if(A[mid] == target)  
            {  
                return mid;  
            }  
            //         
            if(A[begin] <= A[mid])  
            {  
                //  target      ，   ，        ，    ，          
                if(A[begin] <= target && target < A[mid])  
                    end = mid - 1;  
                else  
                    begin = mid + 1;  
            }  
            //else         
            else  
            {  
                //  target      ，   ，        ，       ，          
                if(A[mid] < target && target <= A[end])  
                    begin = mid + 1;  
                else  
                    end = mid - 1;  
            }  
        }  
        return -1;  
    }  

}

変換元:https://blog.csdn.net/u012243115/article/details/42002283