首页 > 代码库 > leetcode第一刷_Search for a Range

leetcode第一刷_Search for a Range

实际上也是一个二分查找的问题。

要找出范围,决定了当找到这个数时不能马上返回,如果找target最前面的那个位置,只有当这个位置等于target,且这个位置的前一个位置不等于target时,才能返回这个位置。如果找的是target最后面的那个位置,那么只有当这个位置等于target,且这个位置的后一个位置不等于target时,才会返回它。不满足返回条件时,下一次递归走什么位置也不一样,找前面的时候,小于等于都往前半走,找后面的时候,大于等于都往后半半儿找。

觉得我实现的有点丑,往前往后找其实差别不大,但是想合起来好像还不太好和。还有一点,但往前找找不到的时候,往后找就不用找了,直接返回没找到,道理显然。

class Solution {
public:
    int findFirst(int A[], int start, int end, int target, int n){
        if(start>end)   return -1;
        int mid = (start+end)/2;
        if(A[mid] == target&&(mid==0||A[mid]!=A[mid-1]))
            return mid;
        else if(A[mid]>=target)
            return findFirst(A, start, mid-1, target, n);
        else
            return findFirst(A, mid+1, end, target, n);
    }
    int findEnd(int A[], int start, int end, int target, int n){
        if(start>end)   return -1;
        int mid = (start+end)/2;
        if(A[mid] == target&&(mid==n-1||A[mid]!=A[mid+1]))
            return mid;
        else if(A[mid]>target)
            return findEnd(A, start, mid-1, target, n);
        else
            return findEnd(A, mid+1, end, target, n);
    }
    vector<int> searchRange(int A[], int n, int target) {
        int mstart, mend;
        vector<int> res;
        if(A == NULL || n <=0)  return res;
        mstart = findFirst(A, 0, n-1, target, n);
        if(mstart == -1){
            res.push_back(-1);
            res.push_back(-1);
        }else{
            res.push_back(mstart);
            res.push_back(findEnd(A, mstart, n-1, target, n));
        }
        return res;
    }
};