34. Find First and Last Position of Element in Sorted Array

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. (link)

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]

Solution

Lower Bound and Upper bound Concept

We use the concept of lower bound and upper bound in binary search (link).

From the lower bound concept, we obtain the index of the nearest element that is greater or equal to the target.

From the upper bound concept, we obtain the index of the nearest element that is greater than the target.

First, we ascertain the lower bound of the target, assuming it to be lb.

We halt the process if the following conditions are met:

• If the element present at index lb is not the same as the target, then we can terminate the process because we cannot find any element identical to the target.

• If lb is pointing to nums.length, then we can also stop because no element exists with the value target.

Next, we determine the upper bound of the target. This operation returns the index of the element that is just greater than the target. Hence, we subtract 1 from the upper bound index before returning it.

class Solution {

    public int lowerBound(int[] nums, int target){
        int low = 0;
        int high = nums.length-1;

        int ans = nums.length;
        while(low<=high){
            int mid = (low+high)/2;

            if(target<=nums[mid]){
                ans = mid;
                high = mid -1;
            }
            else{
                low = mid +1;
            }
        }
        return ans;
    }

    public int upperBound(int[] nums, int target){
        int low = 0;
        int high = nums.length-1;

        int ans = nums.length;
        while(low<=high){
            int mid = (low+high)/2;

            if(target<nums[mid]){
                ans = mid;
                high = mid -1;
            }
            else{
                low = mid +1;
            }
        }
        return ans;
    }

    public int[] searchRange(int[] nums, int target) {

        int lb = lowerBound(nums,target);

        if(lb==nums.length || nums[lb]!=target) return new int[]{-1,-1};

        return new int[]{lb, upperBound(nums,target)-1};
    }
}

Plain Binary Search

In order to find the first occurrence position, we require one binary search, and for the last occurrence position, we require one more binary search.

To find the first occurrence of the target, we employ the standard binary search template. We verify whether the mid element is equal to the target. If it is, then we store the index into our answer variable first. After the target check:

• If target <= nums[mid], it implies there is a chance that one more index might have the same value as the target. Hence, we move left by eliminating the right half.

• Otherwise, we move right by eliminating the left half.

Note that we also include the equals condition because we aim for the least index of the target. If we don't include it, we obtain the highest index.

To find the last occurrence of the target, we follow the same process, except we remove the equals condition and only keep the condition for greater values.

class Solution {

    public int firstOcurrence(int[] nums, int target){
        int low = 0;
        int high = nums.length-1;

        int first = -1;

        while(low<=high){
            int mid = (low+high)/2;

            if(target==nums[mid]){
                first = mid;
            }

            if(target<=nums[mid]){
                high = mid - 1;
            }
            else{
                low = mid + 1;
            }
        }

        return first;
    }

    public int lastOcurrence(int[] nums, int target){
        int low = 0;
        int high = nums.length-1;

        int last = -1;

        while(low<=high){
            int mid = (low+high)/2;

            if(target==nums[mid]){
                last = mid;
            }

            if(target<nums[mid]){
                high = mid - 1;
            }
            else{
                low = mid + 1;
            }
        }

        return last;
    }

    public int[] searchRange(int[] nums, int target) {

        int first = firstOcurrence(nums,target);

        if(first==-1) return new int[]{-1,-1};

        return new int[]{first, lastOcurrence(nums,target)};
    }
}