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

Posted on | In

Problem

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:

1
2
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

1
2
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Explanation

  1. The array is sorted and and we need the runtime be $O(\log n)$, so we use binary search.

  2. To find the first and last index of the target elements, when we do binary search, we do not need to consider the case if target == nums[mid], return mid. We can keep divide and conquer the array.

  3. To find the first index of the target, when target == nums[mid] or target < nums[mid], the right is moving toward mid and we check the left first. To find the last index of the target, when target == nums[mid] or target > nums[mid], the left is moving toward mid and we check the right first.

Solution 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
class Solution {
    int findFirst(int[] nums, int target) {
        int left = 0, right = nums.length-1;
        while (left + 1 < right) {
            int mid = left + (right-left)/2;
            if (target > nums[mid]) {
                left = mid;
            } else {
                right = mid;
            }
        }
        if (nums[left] == target) return left;
        if (nums[right] == target) return right;
        return -1;
    }
    int findLast(int[] nums, int target) {
        int left = 0, right = nums.length-1;
        while (left + 1 < right) {
            int mid = left + (right-left)/2;
            if (target < nums[mid]) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (nums[right] == target) return right;
        if (nums[left] == target) return left;
        return -1;
    }
    public int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0) return new int[]{-1, -1};
        int start = findFirst(nums, target);
        if (start == -1) return new int[]{-1, -1};
        int end = findLast(nums, target);
        return new int[]{start, end};
    }
}

Solution 2

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
class Solution {
    int findLeft(int[] nums, int target) {
        int left = 0, right = nums.length-1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (nums[left] == target) {
            return left;
        } else {
            return -1;
        }
    }

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

    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[2];
        if (nums == null || nums.length == 0) {
            res[0] = -1;
            res[1] = -1;
            return res;
        }
        res[0] = findLeft(nums, target);
        res[1] = findRight(nums, target);

        return res;
    }
}

Solution 3

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
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[]{-1, -1};
        if(nums == null || nums.length == 0) return res;
        // find the left-end
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        res[0] = nums[left] == target ? left : -1;

        // find right-end
        if (res[0] != -1) {
            if (left == nums.length - 1 || nums[left + 1] != target) {
                res[1] = left;
            } else {
                right = nums.length - 1;
                while (left < right) {
                    int mid = left + ((right - left) >> 1) + 1;
                    if (nums[mid] > target) {
                        right = mid - 1;
                    } else {
                        left = mid;
                    }
                }
                res[1] = right;
            }
        }
        return res;
    }
}