Month: November 2023

Difficulty: medium
Topics: array, binary search

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

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

You must 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]

Leetcode problem 34

Solution

The way to handle this is by finding start and end pos separately.

We can do this by implementing separate binary searches to find lower bound and higher bound of target.

OR just make one binary search to find the lower bound of target and find the end position by finding the lower bound of (target+1).

The first approach is shown below:

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        // if it's empty,
        if (nums.size() == 0){
            vector<int> res = {-1, -1};
            return res;
        }
        
        // search left bound
        int l = 0, r = nums.size()-1;
        int leftrange = 0;
        while (l < r){
            int mid = (l+r)/2;
            if (nums[mid] >= target) r = mid;
            else l = mid+1;
        }
        if (nums[l] != target) leftrange = -1; 
        else leftrange = l; 

        // search right bound
        l = 0, r = nums.size()-1;
        int rightrange = 0;
        while (l < r){
            int mid = (l+r+1)/2;
            if (nums[mid] <= target) l = mid;
            else r = mid-1;
        }
        if (nums[l] != target) rightrange = -1;
        else rightrange = l; 
        
        // print the result
        vector<int> res = {leftrange, rightrange};
        return res;
    }
};

By only implementing binSearch that finds lower bound:

class Solution {
private:
    int lower_bound(vector<int>& nums, int low, int high, int target){
        while(low <= high){
            int mid = (low + high) >> 1;
            if(nums[mid] < target){
                low = mid + 1;
            }
            else{
                high = mid - 1;
            }
        }
        return low;
    }

public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int low = 0, high = nums.size()-1;
        int startingPosition = lower_bound(nums, low, high, target);
        int endingPosition = lower_bound(nums, low, high, target + 1) - 1;
        if(startingPosition < nums.size() && nums[startingPosition] == target){
            return {startingPosition, endingPosition};
        }
        return {-1, -1};
    }
};

Since we already have a built in lower_bound library function, we can use that:

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int startingPosition = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
        int endingPosition = lower_bound(nums.begin(), nums.end(), target+1) - nums.begin() - 1;
        if(startingPosition < nums.size() && nums[startingPosition] == target){
            return {startingPosition, endingPosition};
        }
        return {-1, -1};
    }
};