Search for a Range

　　关于二分法搜索的题目，真是多得不能再多。当然标准的二分搜索是核心，在此之上作变化。

　　常见的有搜索目标值中index最小的，搜索目标值中index最大的。常见的思路是先用二分搜索找到目标值，再往左或者往右依次比较。然而，对于有些输入，比如[1,1,1,1,1,1]这样的数组，算法就退化成了O(n)了。正确的方法仍然是使用二分。

　　就这题而言，可以分作三部：先找最左边的，再找最右边的，最后合并，就是结果。算法复杂度nlog(n)。

　　

class Solution {
public:
    vector<int> searchRange(int A[], int n, int target) {
        vector<int> res;
        if(n==0)
            return res;
        int left=searchRangeLeft(A,n,target);
        int right=searchRangeRight(A,n,target);
        if(left!=-1)
            return res;
        res.push_back(left);
        res.push_back(right);
        return res;
    }

    int searchRangeRight(int A[],int n,int target){
        int l=0;
        int r=n-1;
        int m;
        int res=n;
        
        while(l<=r)
        {
            m=(l+r)/2;
            if(A[m]==target){
                if(m<res)
                    res=m;
                r=m-1;
            }
            else if(target<A[m])
            {
                r=m-1;
            }
            else
            {
                l=m+1;
            }
        }
        if(res==n)
            res=-1;
        return res;
    }

    int searchRangeLeft(int A[],int n,int target){
        int l=0;
        int r=n-1;
        int m;
        int res=-1;
        
        while(l<=r)
        {
            m=(l+r)/2;
            if(A[m]==target){
                if(m>res)
                    res=m;
                l=m+1;
            }
            else if(target<A[m])
            {
                r=m-1;
            }
            else
            {
                l=m+1;
            }
        }
        return res;
    }
};

　　还看到另外一种解法，只需要求目标值的最大index。

　　

class Solution {  
public:  
    vector<int> searchRange(int A[], int n, int target) {  
        // Start typing your C/C++ solution below  
        // DO NOT write int main() function  
        vector<int> res(2);  
        res[0] = binarySearch(A, n, target - 1) + 1;  
        res[1] = binarySearch(A, n , target);  
        if(res[1] == -1 || A[res[1]] != target){  
            res[0] = -1;  
            res[1] = -1;  
        }  
        return res;  
    }  
    int binarySearch(int A[], int n, int target){  
        int l = 0;  
        int r = n -1;  
        int m = (l+r)/2;  
        int ret = -1;  
        while(l<=r){  
            if(A[m] > target){  
                r = m - 1;  
                m = (l+r)/2;  
            }  
            else{  
                ret = m;  
                l = m + 1;  
                m = (l+r)/2;  
            }  
        }  
        return ret;  
    }  
};  

　　这一解法我持保留态度，因为它的binarySearch函数返回的结果其实是不明确的，也就是说，需要对返回的结果作进一步的判断才能确定是否找到了目标值。如果从工程的角度而言，这样无异于给未来埋了一个定时炸弹。