Skip to content

Crack SDE

Most of the content are generated by AI, with human being reviewed, edited, and revised

Menu
  • Home
  • Daily English Story
  • Tech Interviews
  • Cloud Native
  • DevOps
  • Artificial Intelligence
Menu

Find the first and last occurrence in an array

Posted on 10/09/202311/13/2023 by user

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:

  • Click to share on Facebook (Opens in new window) Facebook
  • Click to share on X (Opens in new window) X

Related

Recent Posts

  • LC#622 Design Circular Queue
  • Started with OpenTelemetry in Go
  • How Prometheus scrap works, and how to find the target node and get the metrics files
  • How to collect metrics of container, pods, node and cluster in k8s?
  • LC#200 island problem

Recent Comments

  1. another user on A Journey of Resilience

Archives

  • May 2025
  • April 2025
  • February 2025
  • July 2024
  • April 2024
  • January 2024
  • December 2023
  • November 2023
  • October 2023
  • September 2023
  • August 2023
  • June 2023
  • May 2023

Categories

  • Artificial Intelligence
  • Cloud Computing
  • Cloud Native
  • Daily English Story
  • Database
  • DevOps
  • Golang
  • Java
  • Leetcode
  • Startups
  • Tech Interviews
©2025 Crack SDE | Design: Newspaperly WordPress Theme
Manage Cookie Consent
To provide the best experiences, we use technologies like cookies to store and/or access device information. Consenting to these technologies will allow us to process data such as browsing behavior or unique IDs on this site. Not consenting or withdrawing consent, may adversely affect certain features and functions.
Functional Always active
The technical storage or access is strictly necessary for the legitimate purpose of enabling the use of a specific service explicitly requested by the subscriber or user, or for the sole purpose of carrying out the transmission of a communication over an electronic communications network.
Preferences
The technical storage or access is necessary for the legitimate purpose of storing preferences that are not requested by the subscriber or user.
Statistics
The technical storage or access that is used exclusively for statistical purposes. The technical storage or access that is used exclusively for anonymous statistical purposes. Without a subpoena, voluntary compliance on the part of your Internet Service Provider, or additional records from a third party, information stored or retrieved for this purpose alone cannot usually be used to identify you.
Marketing
The technical storage or access is required to create user profiles to send advertising, or to track the user on a website or across several websites for similar marketing purposes.
Manage options Manage services Manage {vendor_count} vendors Read more about these purposes
View preferences
{title} {title} {title}