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

Posted on | In ,

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

No.1

Input: nums = [5,7,7,8,8,10], target = 8

Output: [3,4]

No.2

Input: nums = [5,7,7,8,8,10], target = 6

Output: [-1,-1]

Code

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
public int[] searchRange(int[] nums, int target) {
    int[] result = {-1, -1};
    
    if (nums == null || nums.length < 1)
        return result;

    int left = binarySearch(nums, target, 0, nums.length - 1, true);

    if (nums[left] != target)
        return result;

    result[0] = left;

    int right = binarySearch(nums, target, left, nums.length, false) - 1;

    result[1] = right;

    return result;
}

private int binarySearch(int[] nums, int target, int left, int right, boolean isLeft) {
    while (left < right) {
        int mid = left + (right - left) / 2;

        if ((isLeft && nums[mid] < target) || (!isLeft && nums[mid] <= target))
            left = mid + 1;
        else
            right = mid;
    }

    return right;
}