First, Last Occurrences and Count in an Array

Occurrences in Sorted Array One Shot

What are Occurrences in a Sorted Array?

An occurrence means the position where a target value appears in an array.

In a sorted array, the same values always appear together as one continuous block. This makes it easier to find the first position, last position, or total count of a target value using Binary Search.

Common occurrence-based problems include:

• First Occurrence in a Sorted Array

• Last Occurrence in a Sorted Array

• Count Occurrences in a Sorted Array

How Occurrence-Based Binary Search Works

Normal Binary Search stops when the target is found.

Occurrence-based Binary Search does one extra thing: even after finding the target, it continues searching on one side to find the required boundary.

Most occurrence problems follow the same simple process:

• Initialize low, high, and answer.

• Find the middle index.

• Compare the middle element with the target.

• If the target is found, store the index.

• Move left for first occurrence.

• Move right for last occurrence.

• Use first and last positions to count total occurrences.

The sorted order is important because it tells which half can be ignored safely.

First Occurrence in a Sorted Array

Given a sorted array and a target value, find the first position where the target appears. If the target does not exist, return -1.

For a detailed explanation, see the original TUF blog: First Occurrence

Algorithm

• Start with two pointers: low = 0, which marks the start of the search range and high = n - 1, which marks the end of the search range.

• Create a variable ans = -1. This stores the first occurrence if we find it. It stays -1 if the target is not present.

• Repeat while low <= high:

  • Find mid = low + (high - low) / 2.

  • If arr[mid] == target: Store mid in ans. Move left by setting high = mid - 1. Because there may be an earlier occurrence on the left side.

  • If arr[mid] < target: Move right by setting low = mid + 1. Because the target can only be on the right side in a sorted array.

  • If arr[mid] > target: Move left by setting high = mid - 1. Because the target can only be on the left side.

• After the loop ends Return ans. If it is still -1, the target was not found.

• Edge cases:

  • If the array is empty, return -1.

  • If the target is smaller than all elements or larger than all elements, return -1.

  • If all elements are equal to the target, the first index should be returned.

Dry Run

Complexity Analysis

Time Complexity: O(log₂ N), N is the size of array, because we cut the search space in half at every step.

Space Complexity: O(1), because we only use a few extra variables.

Last Occurrence in a Sorted Array

Given a sorted array and a target value, find the last position where the target appears. If the target does not exist, return -1.

For a detailed explanation, see the original TUF blog: Last Occurrece

Algorithm

• Start with two pointers: low = 0, which marks the start of the search range. high = n - 1, which marks the end of the search range.

• Create a variable ans = -1. This stores the first occurrence if we find it. It stays -1 if the target is not present.

• Repeat while low <= high:

  • Find mid = low + (high - low) / 2.

  • If arr[mid] == target: Store mid in ans. Move right by setting left = mid + 1 Because there may be an later occurrence on the left side.

  • If arr[mid] < target: Move right by setting low = mid + 1. Because the target can only be on the right side in a sorted array.

  • If arr[mid] > target: Move left by setting high = mid - 1. Because the target can only be on the left side.

• After the loop ends Return ans. If it is still -1, the target was not found.

• Edge cases:

  • If the array is empty, return -1.

  • If the target is smaller than all elements or larger than all elements, return -1.

  • If all elements are equal to the target, the first index should be returned.

Dry Run

Complexity Analysis

Time Complexity: O(log₂ N), N is the size of array, because binary search divides the array into half each time.

Space Complexity: O(1), because only a few variables are used.

Count Occurrences in a Sorted Array

Given a sorted array and a target value, count how many times the target appears. If the target does not exist, return 0.

For a detailed explanation, see the original TUF blog: Count Occurrences

Algorithm

• First, find the first occurrence of the target using binary search. Use low, high, and ans. Save the leftmost position where the target appears.

• If first occurrence is -1 Return 0. Because the target is not present at all.

• Then find the last occurrence of the target using binary search. Again use low, high, and ans. Save the rightmost position where the target appears.

• Compute the count using: count = last - first + 1 Because both ends are included in the block.

• Return count.

• Edge cases:

  • If the array is empty, return 0.

  • If the target is not present, return 0.

  • If the target appears once, the count will be 1.

  • If all elements are the target, the count will be n.

Dry Run

Complexity Analysis

Time Complexity: O(log₂ N), N is the size of array, because we cut the search space in half at every step.

Space Complexity: O(1), because we only use a few extra variables.