Question

Formatted question description: https://leetcode.ca/all/34.html

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

Level

Medium

Description

Given an array of integers nums sorted in ascending order, 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].

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]

Solution

Since the runtime complexity is restricted to be in the order of O(log n), and the array is sorted, binary search is an ideal solution.

Do binary search two rounds. The first round finds whether the given target is in the array nums, and if target exists, get the index of target (if there are duplicates, find any index that has the number target).

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

If the given target is in the array, do binary search for the second round. Do binary search at both sides of the index found in the first round, and find the leftmost index and the rightmost index of target. In the second round, the loop condition of binary search is that the left pointer is less than the right poiner and the equal case is not included in the loop condition, which is a little different from traditional binary search.

Code

Java

public class Find_First_and_Last_Position_of_Element_in_Sorted_Array {

    class Solution {

        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; // @note: -1 to get right most index

            return targetRange;
        }

        // returns leftmost (or rightmost) index at which `target` should be
        // inserted in sorted array `nums` via binary search.
        private int extremeInsertionIndex(int[] nums, int target, boolean isLeft) {
            int lo = 0;
            int hi = nums.length;

            while (lo < hi) {
                int mid = (lo + hi) / 2;
                if (nums[mid] > target || (isLeft && target == nums[mid])) {
                    hi = mid;
                }
                else {
                    lo = mid+1;
                }
            }

            return lo;
        }
    }
}

// OJ: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
// Time: O(logN)
// Space: O(1)
class Solution {
public:
    vector<int> searchRange(vector<int>& A, int target) {
        if (A.empty()) return {-1,-1};
        int N = A.size(), L = 0, R = N - 1;
        while (L <= R) {
            int M = (L + R) / 2;
            if (A[M] < target) L = M + 1;
            else R = M - 1;
        }
        if (L >= N || A[L] != target) return {-1,-1};
        int left = L;
        L = 0, R = N - 1;
        while (L <= R) {
            int M = (L + R) / 2;
            if (A[M] > target) R = M - 1;
            else L = M + 1;
        }
        return {left, R};
    }
};

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def findRange(left):
            l, r = 0, len(nums) - 1
            m = 0
            while l <= r:
                m = l + (r - l) // 2
                if nums[m] < target:
                    l = m + 1
                elif nums[m] > target:
                    r = m - 1
                elif left and m > 0 and nums[m - 1] == nums[m]:
                    r = m - 1
                elif not left and m + 1 < len(nums) and nums[m + 1] == nums[m]:
                    l = m + 1
                else:
                    return m
            if m < len(nums) and nums[m] == target:
                return m
            else:
                return -1
        return [findRange(True), findRange(False)]

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