Problem Statement

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

Follow up: Could you write an algorithm with O(log n) runtime complexity?

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

Problem Link

Find First and Last Position of Element in Sorted Array - LeetCode

Code

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        
   
        int l1 = 0, h2 = nums.size()-1, mid, h1 = -1;
        
        while(l1<=h2)
        {
            mid = (l1+h2)/2;
            
            if(nums[mid]==target)
            {
                h1 = mid;
                break;
            }
            else if(nums[mid]<target)
                l1 = mid+1;
            else
                h2 = mid-1;
        }
        
        if(h1==-1)
            return vector<int>{-1,-1};
        vector<int> res;
        
        int l2 = h1 + 1;
        l1 = 0;
        h2 = nums.size() - 1;
        
        while(l1<=h1)
        {
            int mid1 = (l1+h1)/2;
            
            if(nums[mid1]==target)
            {
                if(nums[mid1]==nums[l1])
                    break;
                else
                    l1++;
            }
            
            else if(nums[mid1]<target)
                l1 = mid1+1;
            else
                h1 = mid1-1;
                
        }
        res.push_back(l1);
        
        while(l2<=h2)
        {
            int mid2 = (l2+h2)/2;
            
            if(nums[mid2]==target)
            {
                if(nums[mid2]==nums[h2])
                    break;
                else
                    h2--;
            }
            
            else if(nums[mid2]<target)
                l2 = mid2+1;
            else
                h2 = mid2-1;
        }
        res.push_back(h2);
        
        return res;
            
        
    }
}; // Time Complexity = O(logn)