34. Find First And Last Position Of Element In Sorted Array

/**

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

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

 */

See the solution to the problem here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/search/SearchRange.java

The reason to include the below implementation is that it is done in a very clear and concise manner. I have personally asked this question to many folks in interviews and to date no one has given me an answer as simple as that below. So, recommend understanding the logic as its simplicity is beautiful.

Conceptually the problem is very simple, the data is sorted so you are using binary search to search for the desired element. The twist is that you are looking for the first and last index of that element.   So, you can solve for the first index via setting hi as mid via below code. When left is true and mid==target, set hi = mid.

if (nums[mid] > target // mid is greater than target

        //mid is same as target but you are searching for the left most index of the target

        || (left && target == nums[mid]))

And when searching for the rightmost index you move lo to one greater than mid when mid is equal or less than the target. This would return the rightmost index one past the target value, so need to move the index to the left.

Here is the code:

public static int extremeInsertionIndex(int[] nums, int target, boolean left) {
    int lo = 0;
    int hi = nums.length;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (nums[mid] > target // mid is greater than target
                //mid is same as target but you are searching for the left most index of the target
                || (left && target == nums[mid]))
        {
            hi = mid;
        }
        else {
            //target is to the right of the mid
            //or you are searching for the right most index
            lo = mid+1;
        }
    }
    return lo;
}

public int[] searchRange(int[] nums, int target) {
    int[] targetRange = {-1, -1};
    int leftIdx = extremeInsertionIndex(nums, target, true);
    // assert that `leftIdx` is within the array bounds and that `target`
    // is actually in `nums`.
    if (leftIdx == nums.length || nums[leftIdx] != target) {
        return targetRange;
    }
    targetRange[0] = leftIdx;
    targetRange[1] = extremeInsertionIndex(nums, target, false)-1;
    return targetRange;
}