Fixed Point - Leetcode Solution

Problem Statement:

Given an array of integers nums sorted in non-decreasing 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:

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]

Solution:

The given problem can be solved using a binary search approach in O(log n) time complexity.

We can use a binary search to locate the left-most occurrence of the target element in the array. Once we find the left-most occurrence of the target element, we can use a binary search again to find the right-most occurrence of the target element.

Algorithm:

1. Initialize two indices, l and r, to first and last indices of the array respectively.
2. While l <= r, repeat steps 3 to 6:
3. Compute the middle index as mid = (l + r) / 2.
4. If the target element is less than middle element, set r = mid - 1.
5. Else if the target element is greater than middle element, set l = mid + 1.
6. Otherwise, store the index of middle element as candidate_left and set r = mid - 1. This is because we want to keep searching for the left-most occurrence of the target element.
7. If candidate_left is still -1, return [-1, -1]. Otherwise, repeat steps 8 to 11:
8. Set l to 0 and r to the last index of the array.
9. While l <= r, repeat steps 10 to 13:
10. Compute the middle index as mid = (l + r) / 2.
11. If the target element is greater than middle element, set l = mid + 1.
12. Else if the target element is less than middle element, set r = mid - 1.
13. Otherwise, store the index of middle element as candidate_right and set l = mid + 1. This is because we want to keep searching for the right-most occurrence of the target element.
14. Return [candidate_left, candidate_right].

Code:

Here is the implementation of the above algorithm in Python:

class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: l, r = 0, len(nums) - 1 candidate_left, candidate_right = -1, -1

    # Find left-most index of target element
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] < target:
            l = mid + 1
        elif nums[mid] > target:
            r = mid - 1
        else:
            candidate_left = mid
            r = mid - 1
        
    # Target element not found
    if candidate_left == -1:
        return [-1, -1]
    
    l, r = 0, len(nums) - 1
    
    # Find right-most index of target element
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] < target:
            l = mid + 1
        elif nums[mid] > target:
            r = mid - 1
        else:
            candidate_right = mid
            l = mid + 1
            
    return [candidate_left, candidate_right]

1