search-in-rotated-sorted-array

gistfile1.txt

https://oj.leetcode.com/problems/search-in-rotated-sorted-array/

/*
    binary search를 응용하여 해결 가능.
    
    test case [4,5,6,7,8,1,2,3] , 8
              [7,8,1,2,3,4,5,6] , 8
        
    suedo code:    
    if pivot == target return pivot                     
    else if pivot < target
        if(high >= pivot) //right or left side 
            if(high < target) //left side
            else if(high >= target) //right side
        else if(high < pivot) //here
            
    else if pivot > target 
        if low >= pivot //left or right
            if(low > target) //left side
            else if(low <= target) right side 
        else if low < pivot //left 
        
    시간복잡도 : O(logn)
    결과 : equal 처리를 하지않아 1번째 시도 실패. 2번째 통과
*/


class Solution {
public:
    int search(int A[], int n, int target) {
        int low = 0;
        int high = n-1;
        int middle = 0;
        
        while(low <= high) {
            middle = (low + high)/2;
             
            if(A[middle] == target) {
                
                return middle;
            } else if(A[middle] < target) {
                if(A[high] >= A[middle]) { 
                    if(A[high] < target) { //left side
                        high = middle-1;
                    } else if(A[high] >= target) { //right side
                        low = middle+1;
                    }
                } else if(A[high] < A[middle]) { //this range has cut part
                        low = middle+1;                    
                }
            } else if(A[middle] > target) {
                 if(A[low] > A[middle]) { //this range has cut part
                        high = middle-1;
                } else if(A[low] <= A[middle]) { 
                    if(A[low] > target) { //right side
                        low = middle+1;
                    } else if(A[low] <= target) { //right side
                        high = middle-1;
                    }                                       
                }
            }
        }
        
        return -1;
    }
};