Day 21: Find First and Last Position of Element in Sorted Array: Binary Search - leetcode - Python3

 

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]

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums is a non-decreasing array.
• -109 <= target <= 109

SOLUTION

class Solution:

    def searchRange(self, nums: List[int], target: int) -> List[int]:

        left = self.search(nums, target, True)

        right = self.search(nums, target, False)

        return [left, right]

    def search(self, nums, target, leftBias):

        l, r = 0, len(nums)-1

        i = -1

        while l <= r:

            mid: int = (l+r)//2

            if target > nums[mid]:

                l = mid+1

            elif target < nums[mid]:

                r = mid-1

            else:

                i = mid

                if leftBias:

                    r = mid-1

                else:

                    l = mid+1

        return i

Time Complexity: O(log n)

Space Complexity:O(1)

How it works:

The searchRange function first calls the search function to find the index of the first occurrence of target in nums. The search function works by using a binary search algorithm. A binary search algorithm works by repeatedly dividing the search space in half and then searching the half that is more likely to contain the target. The search function starts by setting the left and right pointers to the beginning and end of the search space, respectively. The function then repeatedly does the following:

1. Calculate the midpoint of the search space.
2. Compare the target to the element at the midpoint.
3. If the target is equal to the element at the midpoint, return the midpoint index.
4. If the target is less than the element at the midpoint, set the right pointer to the midpoint minus 1.
5. If the target is greater than the element at the midpoint, set the left pointer to the midpoint plus 1.

The search function continues to do this until the left pointer is greater than or equal to the right pointer. If the left pointer is greater than or equal to the right pointer, then the target is not found in the search space.

Once the search function has found the index of the first occurrence of target in nums, the searchRange function then calls the search function again to find the index of the last occurrence of target in nums. The search function is called with the leftBias argument set to False. This tells the search function to search for the last occurrence of target in nums.

The searchRange function then returns a list containing the index of the first occurrence of target in nums and the index of the last occurrence of target in nums.