By Long Luo

This article is the solution 3 Approaches: DP, Recursion, Math of Problem 34. Find First and Last Position of Element in Sorted Array.

Here shows 2 Approaches to slove this problem: Brute Force and Binary Search.

Brute Force

The easiest method is scan the array from left to right. Use two variables to record the index of the first and last element \(\textit{target}\). The time complexity is \(O(n)\).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public static int[] searchRange(int[] nums, int target) {
    int[] ans = {-1, -1};
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        if (nums[i] == target && ans[0] == -1) {
            ans[0] = i;
        } else if (nums[i] > target && ans[0] >= 0) {
            ans[1] = i - 1;
            return ans;
        }
    }

    if (ans[0] >= 0) {
        ans[1] = len - 1;
    }

    return ans;
}

Analysis

• Time Complexity: \(O(n)\)
• Space Complexity: \(O(1)\)

Binary Search

Since the array is sorted in ascending order, so we can binary search to speed up the search.

Considering the start and end positions of target, in fact, what we are looking for is “the first position in the array equal to target” (recorded as \(\textit{leftIdx}\) ) and “the first position greater than The position of target minus one” (recorded as \(\textit{rightIdx}\) ).

In binary search, looking for \(\textit{leftIdx}\) is to find the first index greater than or equal to target in the array, and looking for \(\textit{rightIdx}\) is to find the first index greater than target in the array index of target, then decrement the index by one.

Finally, since \(\textit{target}\) may not exist in the array, we need to re-check the two indices we got \(\textit{leftIdx}\) and \(\textit{rightIdx}\) to see if they meet the conditions, if so It returns \([\textit{leftIdx}, \textit{rightIdx}]\), if it does not match, it returns \([-1, -1]\).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

public static int[] searchRange_bs(int[] nums, int target) {
    int[] ans = {-1, -1};

    if (nums == null || nums.length <= 0) {
        return ans;
    }

    ans[0] = binarySearchLeft(nums, target);
    ans[1] = binarySearchRight(nums, target);

    return ans;
}

public static int binarySearchLeft(int[] arr, int target) {
    if (arr[arr.length - 1] < target) {
        return -1;
    }

    int left = 0;
    int right = arr.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return arr[left] == target ? left : -1;
}

public static int binarySearchRight(int[] arr, int target) {
    if (arr[0] > target) {
        return -1;
    }

    int left = 0;
    int right = arr.length - 1;
    while (left < right) {
        int mid = left + (right - left + 1) / 2;
        if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid;
        }
    }

    return arr[left] == target ? left : -1;
}

Analysis

• Time Complexity: \(O(\log n)\)
• Space Complexity: \(O(1)\)

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗