Find the first and last occurrence in an array

To find the first occurrence of a target value in a sorted array using binary search, the algorithm needs to be slightly modified from the standard binary search. The goal is to continue searching even after finding the target, to ensure that it’s the first occurrence.

package main

import (
    "fmt"
)

func findFirstOccurrence(nums []int, target int) int {
    low, high := 0, len(nums)-1
    result := -1

    for low <= high {
        mid := low + (high-low)/2

        if nums[mid] == target {
            result = mid
            high = mid - 1 // Continue searching in the left half
        } else if nums[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }

    return result
}

func main() {
    nums := []int{1, 2, 2, 3, 4, 5, 6}
    target := 2
    result := findFirstOccurrence(nums, target)
    fmt.Println("First occurrence of target is at index:", result) // Output: 1
}

In this implementation:

The function findFirstOccurrence performs a binary search on the array nums to find the target.
If target is found (nums[mid] == target), instead of returning immediately, the search continues in the left half of the array (high = mid - 1) to check if there is an earlier occurrence of the target.
If nums[mid] < target, the search continues in the right half; if nums[mid] > target, it continues in the left half.
The variable result is used to store the index of the first occurrence found so far. If the target is not found at all, result remains -1.

This modification ensures that the algorithm finds the first occurrence of the target in a sorted array.

Similarly, to find the last occurrence of the target, modify the standard binary search algorithm so that it continues searching even after finding an instance of the target, aiming to find the last occurrence.

package main

import (
    "fmt"
)

func findLastOccurrence(nums []int, target int) int {
    low, high := 0, len(nums)-1
    result := -1

    for low <= high {
        mid := low + (high-low)/2

        if nums[mid] == target {
            result = mid  // Record the occurrence
            low = mid + 1 // Continue searching in the right half
        } else if nums[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }

    return result
}

func main() {
    nums := []int{1, 2, 2, 3, 4, 5, 6}
    target := 2
    result := findLastOccurrence(nums, target)
    fmt.Println("Last occurrence of target is at index:", result) // Output: 2
}

In this implementation:

The function findLastOccurrence performs a binary search on the array nums to find the target.
If target is found (nums[mid] == target), the index is recorded, and the search continues in the right half of the array (low = mid + 1) to check for a later occurrence.
If nums[mid] < target, the search continues in the right half; if nums[mid] > target, it continues in the left half.
The variable result is used to store the index of the last occurrence found so far. If the target is not found at all, result remains -1.

Share this:

Related