Find First and Last Position of Element in Sorted Array - Python Solution

1. Introduction

The "Find First and Last Position of Element in Sorted Array" problem is a binary search variant, commonly encountered in coding interviews. It involves finding the start and end positions of a target value in a sorted array. This problem tests the ability to tweak the standard binary search algorithm for a slightly different use case, requiring a solution with O(log n) runtime complexity.

Problem

Given an array of integers nums sorted in non-decreasing order, the task is to find the starting and ending position of a given target value. If the target is not found in the array, the function should return [-1, -1].

2. Solution Steps

1. Implement a binary search to find the first occurrence of the target.

2. Implement another binary search to find the last occurrence of the target.

3. Handle cases where the target is not found in the array.

4. Ensure the solution has a runtime complexity of O(log n).

3. Code Program

def searchRange(nums, target):
    def binarySearchLeft(nums, target):
        # Binary search to find the left boundary (first occurrence)
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left

    def binarySearchRight(nums, target):
        # Binary search to find the right boundary (last occurrence)
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] <= target:
                left = mid + 1
            else:
                right = mid - 1
        return right

    left, right = binarySearchLeft(nums, target), binarySearchRight(nums, target)
    # Check if the target is not in the array
    if left <= right:
        return [left, right]
    return [-1, -1]

# Testing the function with examples
print(searchRange([5,7,7,8,8,10], 8))
print(searchRange([5,7,7,8,8,10], 6))
print(searchRange([], 0))

Output:

[3, 4]
[-1, -1]
[-1, -1]

Explanation:

1. Binary Search for Left Boundary: The binarySearchLeft function finds the first occurrence of the target, defining the left boundary.

2. Binary Search for Right Boundary: The binarySearchRight function finds the last occurrence of the target, defining the right boundary.

3. Boundary Check: After finding both boundaries, the function checks if the target exists in the array.

4. Return Value: If the target is found, the function returns the indices of the first and last occurrences. If not, it returns [-1, -1].

5. O(log n) Complexity: Both binary search operations contribute to the overall logarithmic runtime complexity.