Problem 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:

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]

Solution:

First, let’s find the left boundary of the range. We initialize the range to [left=0, right=n-1]. In each step, calculate the middle element mid = left+(right-left)/2. Now according to the relative value of A[mid] to target, there are three possibilities:

  1. If A[mid] < target, the target range must begins on the right of mid (hence left = mid+1 for the next iteration)
  2. If A[mid] > target, it means the range must begins on the left of mid (right = mid-1)
  3. If A[mid] = target, then the range must begins on the left of or at mid (right= mid)

With above mid finding way, the mid will always biased toward left. So we can find the left boundary of target.

That is to say, if we make mid biased toward right, we can find right boundary of target.
We can use mid = left+(right-left)/2 +1.

  1. If A[mid] > target, then the range must begins on the left of mid (right = mid-1)
  2. If A[mid] < target, then the range must begins on the right of mid (hence left = mid+1 for the next iteration)
  3. If A[mid] = target, then the range must begins on the right of or at mid (left= mid)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def findLeft(nums):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if target > nums[mid]: left = mid + 1
                else: right = mid - 1
            return left

        def findRight(nums):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if target >= nums[mid]: left = mid + 1
                else: right = mid - 1
            return right

        left, right = findLeft(nums), findRight(nums)
        return (left, right) if left <= right else [-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
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int high= nums.size()-1, low= 0;
        vector<int> res(2);
        
        //base case
        if(nums.size()== 0)
            return vector<int> {-1, -1};
        
        //search for left side
        while(low< high){
            int mid= low+(high-low)/2; //with this mid finding, the mid will always biased toward left 
            if(target> nums[mid])
                low= mid+1;
            else
                high= mid;
        }
        
        res[0] = (target == nums[low])? low: -1;
        high= nums.size()-1;
        
        while(low< high){
            int mid= low+(high-low)/2 +1; //notice for the mid value, add one so it will biased toward right
            if(target>=nums[mid])
                low= mid;
            else
                high= mid-1;
        }
        res[1] = (target == nums[high])? high: -1;
        
        return res;
    }
};

time complexity: $O(logn)$
space complexity: $O(1)$
reference:
https://goo.gl/hL7qEx