Find First and Last Position of an Element in a Sorted Array

In this tutorial, we will solve the Python problem in which we need to find the first and last position of an element in a sorted array. The problem statement is that we have given an array of integers sorted in non-decreasing order, and find the starting and ending position of a given target value.

Example -

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]

Let's understand the following solutions.

Solution - 1: A naïve Approach

In this approach, we iterate on the elements of a given array and check elements in an array and keep track of the first and last occurrence of the found element's index. Let's understand the following example.

Example -

def find_first_and_last_occurrence(arr, target):
    first_occurrence = -1
    last_occurrence = -1
    
    new_list = []

    for i in range(len(arr)):
        if arr[i] == target:
            if first_occurrence == -1:
                first_occurrence = i
            last_occurrence = i
    new_list.append(first_occurrence)
    new_list.append(last_occurrence)

    return new_list

# Test the function
if __name__ == "__main__":
    given_array = [1, 2, 3, 4, 4, 5, 6, 4]
    target_element = 18

    result = find_first_and_last_occurrence(given_array, target_element)
    print(result)

Output:

[-1, -1]

Explanation -

In the above code, we define the find_first_and_last_occurrence() function that takes an array (arr) and the target element (target) as input. We initialize two variables, first_occurrence, and last_occurrence, to store the indices of the first and last occurrences of the target element in the array.

We then iterate through the array using a for loop and check each element against the target. If we find a match, we update the first_occurrence index if it's the first time we encounter the target element. We keep updating the last_occurrence index to the latest occurrence of the target element as we traverse the array.

Finally, we return the first_occurrence and last_occurrence indices.

The time complexity will be O(n) and auxiliary space will be O(1).

Solution - 2: Using Binary Search

Let's solve this problem using the binary search algorithm.

Example -

def find_first_occurrence(arr, target):
    left, right = 0, len(arr) - 1
    first_occurrence = -1

    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] == target:
            first_occurrence = mid
            right = mid - 1
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return first_occurrence


def find_last_occurrence(arr, target):
    left, right = 0, len(arr) - 1
    last_occurrence = -1

    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] == target:
            last_occurrence = mid
            left = mid + 1
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return last_occurrence


def find_first_and_last_occurrence(arr, target):
    new_list = []
    first_occurrence = find_first_occurrence(arr, target)
    last_occurrence = find_last_occurrence(arr, target)
    return [first_occurrence, last_occurrence]

# Test the function
if __name__ == "__main__":
    given_array = [1, 2, 3, 4, 4, 5, 6, 7]
    target_element = 4

    result = find_first_and_last_occurrence(given_array, target_element)
    print(result)

In the above code, we first define two binary search functions, find_first_occurrence and find_last_occurrence, to find the indices of the first and last occurrences of the target element in the sorted array, respectively.

Then, the find_first_and_last_occurrence function uses these two binary search functions to get the first and last occurrence indices of the target element in the given array.

The test code at the end demonstrates how to use the function with an example sorted array and target element, printing the first and last occurrence indices if the element is found or a message if the element is not present in the array.

Solution - 3:

To get the first occurrence, the first binary search looks for any occurrence of the target number in the array. When a match is found, we record the index and continue searching in the left sub-array, i.e., the elements on the left side of the current index.

The same process will follow in right sub-array to find last occurrence of the number. Let's understand the following example.

Example -

def find_first_occurrence(arr, target):
    left, right = 0, len(arr) - 1
    first_occurrence = -1

    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] == target:
            first_occurrence = mid
            right = mid - 1
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return first_occurrence


def find_last_occurrence(arr, target):
    left, right = 0, len(arr) - 1
    last_occurrence = -1

    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] == target:
            last_occurrence = mid
            left = mid + 1
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return last_occurrence


def find_first_and_last_occurrence(arr, target):
    first_occurrence = find_first_occurrence(arr, target)
    last_occurrence = find_last_occurrence(arr, target)
    return [first_occurrence, last_occurrence]


# Test the function
if __name__ == "__main__":
    given_array = [1, 2, 3, 4, 4, 5, 6, 7]
    target_element = 4

    result = find_first_and_last_occurrence(given_array, target_element)
    print(result)

Output:

[3, 4]

Solution - 3: Using Inbuilt Functions

Let's understand the following example.

Example -

def find_first_and_last_occurrence(arr, target):
    first_occurrence = -1
    last_occurrence = -1

    try:
        first_occurrence = arr.index(target)
        last_occurrence = len(arr) - arr[::-1].index(target) - 1
    except ValueError:
        pass

    return [first_occurrence, last_occurrence]

# Test the function
if __name__ == "__main__":
    given_array = [1, 2, 3, 4, 4, 5, 6, 7]
    target_element = 10

    result = find_first_and_last_occurrence(given_array, target_element)
    print(result)

Output:

[3, 4]

Explanation -

In this solution, the index() method is used to find the index of the first occurrence of the target element in the list. To find the last occurrence, we use index() again, but this time on a reversed version of the list (arr[::-1]) and then calculate the last occurrence's index relative to the original list.

Next TopicFinger Search Tree Data Structure

← prev next →