Đếm số số 0 trong mảng nhị phân đã sắp xếp bằng C++

Mô tả bài toán

Cho mảng chỉ chứa 0 và 1, đã sắp xếp (1 trước, 0 sau). Đếm số lượng 0.

Ví dụ

arr={1,1,1,0,0,0,0} → Output: 4.

Giải thuật

• Tuyến tính O(N): Tìm chỉ số 0 đầu tiên.
• Binary search O(log N): Tìm chỉ số 0 đầu tiên (lower bound của 0). Số 0 = n - firstZeroIndex.

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

#include <iostream>
using namespace std;

int findFirstZero(int arr[], int l, int r) {
    if (r >= l) {
        int mid = l + (r-l)/2;
        if ((mid==0 || arr[mid-1]==1) && arr[mid]==0) return mid;
        if (arr[mid]==1) return findFirstZero(arr, mid+1, r);
        return findFirstZero(arr, l, mid-1);
    }
    return -1;
}

int countZerosArr(int arr[], int n) {
    int idx = findFirstZero(arr, 0, n-1);
    return (idx == -1) ? 0 : n - idx;
}

int main() {
    int arr[] = {1,1,1,1,0,0,0,0,0,0,0};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Count of zeros: " << countZerosArr(arr,n);
    return 0;
}

Đầu ra

The count of zeros in array is 7