(lintcode)61. Search for a Range

class Solution {
public:
    /**
     * @param nums: The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    int binarySearch(vector<int> &nums, int target) {
        // write your code here
        if(nums.size() == 0) return -1;
        int left = 0;
        int right = nums.size() - 1;
        while(left <= right){
            int mid = (left + right) / 2;
            cout<<mid<<endl;
            if(nums[mid] == target){
                int index = mid;
                while(index-1 >= 0 && nums[index-1] == target){
                    index--;
                };
                return index;
            }
            if(nums[mid] < target) left = mid+1;
            else right = mid - 1;
        }
        return -1;
    }
};

模板好！

public:
    /**
     * @param A: an integer sorted array
     * @param target: an integer to be inserted
     * @return: a list of length 2, [index1, index2]
     */
    vector<int> searchRange(vector<int> &A, int target) {
        // write your code here
        vector<int> result;
        if(A.empty()) return vector<int> {-1, -1};
        int lb = -1;
        int ub = A.size();
        while(lb + 1 < ub){
            int mid = lb + (ub - lb) / 2;
            if(target > A[mid]) lb = mid;
            else ub = mid;
        }
        if(A[lb + 1] != target) return vector<int> {-1,-1};
        result.push_back(lb + 1) ;
        lb = -1, ub = A.size();
        while(lb + 1 < ub){
            int mid = lb + (ub - lb)/2;
            if(target < A[mid]) ub = mid;
            else lb = mid;
        }
         result.push_back(ub - 1) ;
        return result;
        
    }
};