First And Last Occurrence - C++ Solution

1. Introduction

This blog post focuses on a common problem in array processing and binary search algorithms - finding the first and last occurrence of a given number in a sorted array. This problem is a classic example of how binary search can be adapted for various array-based search tasks.

Problem

Given a sorted integer array, the task is to find the index of the first and last occurrence of a given target number. If the target is not present, return (-1, -1).

2. Solution Steps

1. Implement a modified binary search to find the first occurrence of the target.

2. Implement another modified binary search to find the last occurrence of the target.

3. Each modified binary search should focus on either moving left to find the first occurrence or right to find the last occurrence.

4. If the target is not found, return (-1, -1).

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to find the first occurrence of the target
int findFirstOccurrence(const vector<int>& nums, int target) {
    int index = -1, low = 0, high = nums.size() - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (nums[mid] == target) {
            index = mid;
            high = mid - 1; // Move left
        } else if (nums[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return index;
}

// Function to find the last occurrence of the target
int findLastOccurrence(const vector<int>& nums, int target) {
    int index = -1, low = 0, high = nums.size() - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (nums[mid] == target) {
            index = mid;
            low = mid + 1; // Move right
        } else if (nums[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return index;
}

// Main function to find first and last occurrence
pair<int, int> findFirstAndLastOccurrence(const vector<int>& nums, int target) {
    return {findFirstOccurrence(nums, target), findLastOccurrence(nums, target)};
}

int main() {
    vector<int> nums = {2, 5, 5, 5, 6, 6, 8, 9, 9, 9};
    int target = 5;
    auto [first, last] = findFirstAndLastOccurrence(nums, target);
    cout << "First and Last Occurrence: (" << first << ", " << last << ")" << endl;
    return 0;
}

Output:

First and Last Occurrence: (1, 3)

Explanation:

The program implements two modified binary searches to find the first and last occurrences of a target number in a sorted array. For the input array [2, 5, 5, 5, 6, 6, 8, 9, 9, 9] with target 5, the output is (1, 3), indicating that 5 first appears at index 1 and last appears at index 3. In cases where the target is not found, both functions return -1, resulting in the pair (-1, -1).