Smallest Missing Number - C++ Solution

1. Introduction

In this blog post, we'll explore a common problem in the realm of array processing - finding the smallest missing number in a sorted array of distinct, non-negative integers. This problem is significant in areas like data analysis and computer science, where identifying gaps in sequences is crucial.

Problem

Given a sorted array of non-negative distinct integers, the task is to find the smallest missing non-negative element. This involves identifying the first gap in the sequence of integers.

2. Solution Steps

1. Perform a binary search to find the smallest missing number.

2. Check if the middle element of the array is equal to its index.

3. If not, the missing number is either the middle element or in the left half of the array.

4. If the middle element equals its index, then the missing number is in the right half.

5. Repeat the process until the smallest missing number is found.

3. Code Program

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

// Function to find the smallest missing number
int findSmallestMissing(const vector<int>& nums) {
    int low = 0, high = nums.size() - 1;

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

        // Check if the missing number is in the left half
        if (nums[mid] != mid) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    // The smallest missing number is the index of the first number
    // that is not equal to its index
    return low;
}

int main() {
    vector<int> nums = {0, 1, 2, 6, 9, 11, 15};
    cout << "Smallest Missing Number: " << findSmallestMissing(nums) << endl;
    return 0;
}

Output:

Smallest Missing Number: 3

Explanation:

The function findSmallestMissing performs a binary search to locate the first instance where the value does not match the index, indicating the smallest missing number. For example, in the array [0, 1, 2, 6, 9, 11, 15], the smallest missing number is 3. The function handles various scenarios, such as when the missing number is 0 (as in [1, 2, 3, 4, 6, 9, 11, 15]) or when all numbers up to the last are present (as in [0, 1, 2, 3, 4, 5, 6], resulting in 7).