Leetcode: Search for a Range (12ms) solution

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].

Hide Tags

 Array Binary Search

Show Similar Problems

Analysis:

A Binary search problem.


///////////////////////////////////////////////////////////////////
//code  12ms
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int m=nums.size(), l=0, r=m-1, mid=(l+r)/2, flag_find=0;
        //find target first
        while(l<=r){
            if(target<nums[mid]){
                r=mid-1;
                mid=(l+r)/2;
            }
            else if(nums[mid]<target){
                l=mid+1;
                mid=(l+r)/2;
            }
            else{
                flag_find=1;
                break;
            }
        }
        //search the range
        if(flag_find==1){
            //search left
            for(int i=mid-1;i>=0;i--){
                if(nums[i]!=target){
                    l=i+1;
                    break;
                }
                l=0;
            }
            //search right
            for(int i=mid+1;i<m;i++){
                if(nums[i]!=target){
                    r=i-1;
                    break;
                }
                r=m-1;
            }
            vector<int> res;
            res.push_back(l);
            res.push_back(r);
            return res;          
        }
        else{
            vector<int> res;
            res.push_back(-1);
            res.push_back(-1);
            return res;
        }
     
    }
};