Tìm số bị thiếu duy nhất trong mảng đã sắp xếp bằng C++

Mô tả bài toán

Cho mảng đã sắp xếp kích thước N chứa 1..N, thiếu một số. Tìm số thiếu.

Ví dụ

arr={1,2,3,5,6,7} → Output: 4.

Giải thuật

• Duyệt tuyến tính O(N): Kiểm tra arr[i] == i+1.
• Binary search O(log N): So sánh arr[mid] với mid+1. Nếu arr[mid] != mid+1 và arr[mid-1]==mid → mid+1 là thiếu. Nếu arr[mid] != mid+1 → tìm bên trái, ngược lại bên phải.

Mã nguồn C++ (Binary Search)

#include <iostream>
using namespace std;

int findMissingValArray(int arr[], int N) {
    int s=0, e=N-1;
    while (s <= e) {
        int mid = (s+e)/2;
        if (arr[mid] != mid+1 && (mid==0 || arr[mid-1]==mid)) return mid+1;
        if (arr[mid] != mid+1) e = mid-1;
        else s = mid+1;
    }
    return -1;
}

int main() {
    int arr[] = {1,2,3,4,6};
    int N = sizeof(arr)/sizeof(arr[0]);
    cout << "Missing value: " << findMissingValArray(arr,N);
    return 0;
}

Đầu ra

The missing value from the array is 5