Leetcode: Search for a Range

最新推荐文章于 2022-10-14 22:00:00 发布

logic_nut

最新推荐文章于 2022-10-14 22:00:00 发布

阅读量781

点赞数

分类专栏：面试题

本文链接：https://blog.csdn.net/logic_nut/article/details/13502111

版权

面试题专栏收录该内容

50 篇文章

订阅专栏

http://oj.leetcode.com/problems/search-for-a-range/

class Solution {
public:
    // Don't try to find one and then extend to the start direction and end direction
    // The time complexity will become O(N) if all the numbers are identical
    // Another way is to use searchMaxLessThan(), then we only need one helper function
    // But we are going to need more logic on process the returned indices
    int FindFirst(int A[], int n, int target){
        int left=0, right=n-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(A[mid]<target) left=mid+1;
            else if(A[mid]>target) right=mid-1;
            else{
                if(mid==0||A[mid-1]!=target) return mid;
                else right=mid-1;
            }
        }
        return -1;
    }
    int FindLast(int A[], int n, int target){
        int left=0, right=n-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(A[mid]<target) left=mid+1;
            else if(A[mid]>target) right=mid-1;
            else{
                if(mid==(n-1)||A[mid+1]!=target) return mid;
                else left=mid+1;
            }
        }
        return -1;
    }
    vector<int> searchRange(int A[], int n, int target) {
        vector<int> res;
        res.push_back(FindFirst(A,n,target));
        res.push_back(FindLast(A,n,target));
        return res;
    }
};