Find First and Last Position of Element in Sorted Array

The problem of finding the first and last position of an element in a sorted array is a common algorithmic challenge. It can be efficiently solved using binary search, a fundamental algorithm in computer science. To understand this problem and its solution, we'll break it down using first principles.

Understanding the Problem

Input: You are given a sorted array of integers and a target integer.
Output: Your task is to find the starting and ending position of the target integer in the array.
Constraints: The array is sorted, which is a critical piece of information as it allows the use of binary search.

Why Binary Search?

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item until you've narrowed down the possible locations to just one. The key principle here is the "divide and conquer" strategy, which significantly reduces the time complexity compared to a linear search.

Algorithm Overview

Standard Binary Search: First, understand the standard binary search algorithm. It finds the position of a target value within a sorted array. If the target is not present, it returns -1 or a relevant value indicating the target is not found.
Modified Binary Search for First Position: Modify the binary search to find the first occurrence of the target. When the target is found, instead of stopping, continue the search towards the left (lower indices).
Modified Binary Search for Last Position: Similarly, modify the binary search to find the last occurrence of the target. When the target is found, continue the search towards the right (higher indices).

Implementing the Solution

Let's write a Python function to implement this. The function will return a list of two elements: the first and last positions of the target in the array.

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

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

    first = binarySearchLeft(arr, target)
    last = binarySearchRight(arr, target)

    # Check if the target is not present in the array
    if first <= last:
        return [first, last]
    return [-1, -1]

# Example usage
array = [5, 7, 7, 8, 8, 10]
target = 8
print(findFirstAndLast(array, target))  # Output will be [3, 4]

Detailed Explanation

binarySearchLeft: This function is a modified binary search that focuses on finding the leftmost (first) occurrence of the target. When the target is found, it doesn't stop; instead, it moves the right pointer to mid - 1 to continue searching to the left.
binarySearchRight: This function finds the rightmost (last) occurrence of the target. It is similar to binarySearchLeft but continues to search to the right even after finding the target by moving the left pointer to mid + 1.
Final Check: After obtaining the first and last positions, we check if the first position is less than or equal to the last position. If it's not, it means the target is not present in the array, and we return [-1, -1].

This algorithm efficiently solves the problem with a time complexity of O(log n) due to the use of binary search, which is significantly better than a linear search approach with a time complexity of O(n).

Prev Next