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

Trong hướng dẫn này, chúng ta sẽ thảo luận về chương trình tìm số 1 trong mảng nhị phân đã sắp xếp.

Chúng ta sẽ được cung cấp một mảng chỉ chứa 1 và 0. Nhiệm vụ của chúng ta là đếm số lượng 1 hiện diện trong mảng.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
//trả về số lượng 1
int countOnes(bool arr[], int low, int high){
    if (high >= low){
        int mid = low + (high - low)/2;
        if ( (mid == high || arr[mid+1] == 0) && (arr[mid] == 1))
            return mid+1;
        if (arr[mid] == 1)
            return countOnes(arr, (mid + 1), high);
        return countOnes(arr, low, (mid -1));
    }
    return 0;
}
int main(){
    bool arr[] = {1, 1, 1, 1, 0, 0, 0};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Số lượng 1 trong mảng cho trước là " << countOnes(arr, 0, n-1);
    return 0;
}

Kết quả

Số lượng 1 trong mảng cho trước là 4