[LeetCode] 34. Search for a Range

Given an array of integers 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].

For example,

Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Solution

The target is to achieve this algorithm with the runtime complexity of O(log n), therefore we cannot implement regular search method or even achieving this in one pass. The complexity of O(log n) immediately reminds us of Quick Sort. We can compare the middle value of the the array with the target and find out the exact spot of the target.

Hence, we can implement Binary Search.

First, find the left boundary of the range. We initialize the range to [i=0, j=n-1]. In each step, calculate the middle element [mid = (i+j)/2]. Now according to the relative value of A[mid] to target, there are three possibilities:
[1] If A[mid] < target, then the range must begins on the right of mid (hence i = mid+1 for the next iteration)
[2] If A[mid] >= target, it means the range must begins on the left of mid (j = mid)

However, how can we make sure that the return value of this search is the very first one in this array.

Suppose our target is 5, let's take a look at these scenarios.

case 1: [5 7] (A[i] = target < A[j])
case 2: [5 5] (A[i] = target = A[j])
case 3: [3 5] (A[j] = target > A[i])
case 4: [3 7] (A[i] < target < A[j])
case 5: [6 7] (target < A[i] < A[j])

For case 1, and 2, if we follow the above rule, since mid = i => A[mid] = target in these cases, then we would set j = mid. Now the loop terminates and i and j both point to the first 5.
For case 3, since A[mid] < target, then set i = mid+1. The loop terminates and both i and j point to 5.
For all other cases, by the time the loop terminates, A[i] is not equal to 5. So we can easily know 5 is not in the sequence if the comparison fails.

In conclusion, when the loop terminates, the algorithm can always return the index of the number that is bigger or equals the target; otherwise, just return -1.

And for the last index of the target, we can inverse the implement of the Binary Search and start from the back of the array. Or we can actually search for the first index of the first number that is bigger than the target, and the index-1 is the last index of the target.

For [5, 7, 7, 8, 8, 10], we can do binary search for 9, and the binary search will return the index of the first number that is larger or equals 9, which is the last index of target plus one.

The code is shown as below.
Java

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        
        int start = binarySearch(nums,target);
        int end = binarySearch(nums,target+1)-1;
        
        if(start == nums.length || nums[start] != target)
            return new int[]{-1,-1};
        else
            return new int[]{start,end};
    }
    
    private static int binarySearch(int[] nums, int target) {
        
        int low = 0, high = nums.length;
        
        while (low < high) {
            int mid = low + ((high - low) >> 1);

            if (nums[mid] < target) 
                low = mid + 1;
            else 
                high = mid;
        }
        return low;
    }
}

[LeetCode] 34. Search for a Range

For example,

Solution

推荐阅读更多精彩内容