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

LeetCode 34

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]` —

Whenever we are guaranteed that the array will be sorted and we need to find some target number, it is most likely going to be some kind of binary search problem. In this case, it was explicitly stated that we need it to run in O(logn).

So here, we need to find the starting and ending points of our target number, since we can possibly have repeated target numbers. We can probably use the normal binary search and find our target, and then start searching outward until we find our starting and ending points. But this last part is actually going to be linear in time. Consider the worst case scenario, where the entire array is our target number. We find the target it the middle, and will have to go through the entire array to find our left and right indices.

So a clever way to go about this is by modifying the binary search a bit so that we always find the left boundary. So instead of stopping once we find the target, we’ll just stop until the left and right indices cross each other.

# target = 8
[5,7,*7,8,8,10]     # l=0, r=5, m=2, search upper half
[5,7,7,8,*8,10]     # l=3, r=5, m=4, search lower half 
[5,7,7,8,*8,10]     # l=3, r=3, m=3, search lower half
[5,7,7,(8),8,10]    # l=3, r=2, stop, return l

But we’ll perform this twice. Once for the target and once for the target + 1 (we’ll subtract 1 from this index so that it points to our target, and not target + 1).

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        l = self.binSearch(nums, target)
        r = self.binSearch(nums, target + 1) - 1
        if l < len(nums) and nums[l] == target:
            return [l, r]  
        else:
            return [-1,-1]
        
    def binSearch(self, nums, target):
        l, r = 0, len(nums) - 1
        while l <= r:
            m = (r - l) // 2 + l
            if target > nums[m]:
                l = m + 1
            elif target <= nums[m]: # find left boundary
                r = m - 1
        return l