Day 56 #33, #34, Search in Rotated Sorted Array, Search for a Range

Search in Rotated Sorted Array
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.
------------------------------------------------------------
reference with excellent explanation
array is half sorted and the half rotated. Always start with the sorted half then determine which half that our target resides in

class Solution {
public:
    int search(int A[], int n, int target) {
        int start = 0, end = n - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (A[mid] == target) {
                return mid;
            }
            // first half is sorted
            if (A[start] <= A[mid]) {
                if (A[start] <= target && target <= A[mid]) {
                    end = mid - 1;
                }else {
                    start = mid + 1;
                }
            }else { // second half is sorted
                if (A[mid] <= target && target <= A[end]) {
                    start = mid + 1;
                }else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }
};

Update on Dec-15-2014
A[end] would never have a chance to be equal to A[mid]. However, A[start] would in the cases that only contain two elements
that's why A[start] <= A[mid]  

Search for a Range
Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
-----------------------------------------------------------------
注意掌握以下第一种方法
binary search
if hit target, continue searching to expand the range

class Solution {
public:
    void bin (int A[], int start, int end, int target, vector<int> &ret) {
        if (start > end) return;
        int mid = start + (end - start) / 2;
        if (A[mid] == target) {
            if (mid < ret[0] || ret[0] == -1) {
                ret[0] = mid;
                bin(A,start,mid - 1, target, ret);
            }
            if (mid > ret[1]) {
                ret[1] = mid;
                bin(A,mid + 1,end, target, ret);
            }
        }else if (A[mid] < target) {
            bin(A,mid + 1,end, target, ret);
        }else {
            bin(A,start,mid - 1, target, ret);
        }
    }

    vector<int> searchRange(int A[], int n, int target) {
        vector<int> ret(2,-1);
        bin(A,0,n-1,target,ret);
        return ret;
    }
};

class Solution {
public:
    void leftSearch(int A[], int left, int right, int target, vector<int> &range) {
        if (left > right) {
            return;
        }
        
        int mid = left + (right - left) / 2;
        if (A[mid] == target) {
            range[0] = mid;
            leftSearch(A,left,mid - 1,target,range);
        }else if (A[mid] < target) {
            leftSearch(A,mid + 1,right,target,range);
        }
    }
    
    void rightSearch(int A[], int left, int right, int target, vector<int> &range) {
        if (left > right) {
            return;
        }
        
        int mid = left + (right - left) / 2;
        if (A[mid] == target) {
            range[1] = mid;
            rightSearch(A,mid + 1,right,target,range);
        }else if (A[mid] > target) {
            rightSearch(A,left,mid - 1,target,range);
        }
    }
    

    vector<int> searchRange(int A[], int n, int target) {
        int left = 0;
        int right = n - 1;
        vector<int> range(2,-1);
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (A[mid] == target) {
                range[0] = mid;
                range[1] = mid;
                leftSearch(A,left,mid - 1,target,range);
                rightSearch(A,mid + 1,right,target,range);
                break;
            }else if (A[mid] < target) {
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        
        return range;
    }
};

iterative，用2个额外二分法函数，一个是找连续target的起始点，一个是找连续target的终止点
设置好循环的终止条件就行