Example: BinarySearchMaxOnesRow in C++

// BinarySearchMaxOnesRow
#include <iostream>
#include <vector>
#include <algorithm> // Required for std::lower_bound

using namespace std;

// Helper function to find the index of the first '1' using binary search
int findFirstOne(const vector<int>& row) {
    int low = 0, high = row.size() - 1;
    int firstOneIndex = -1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (row[mid] == 1) {
            firstOneIndex = mid;
            high = mid - 1; // Try to find an earlier 1
        } else {
            low = mid + 1; // Look in the right half
        }
    }
    return firstOneIndex;
}

int findRowWithMaxOnesBinarySearch(const vector<vector<int>>& matrix) {
    int numRows = matrix.size();
    if (numRows == 0) return -1;

    int numCols = matrix[0].size();
    if (numCols == 0) return -1;

    int maxOnes = -1;
    int maxRowIndex = -1;

    // Iterate through each row
    for (int i = 0; i < numRows; ++i) {
        // Find the index of the first '1' in the current row
        int firstOneIdx = findFirstOne(matrix[i]);
        // If no '1' is found, firstOneIdx will be -1
        int currentOnes = (firstOneIdx != -1) ? (numCols - firstOneIdx) : 0;

        // Update if current row has more ones
        if (currentOnes > maxOnes) {
            maxOnes = currentOnes;
            maxRowIndex = i;
        }
    }
    return maxRowIndex;
}

int main() {
    // Step 1: Define the example matrix
    vector<vector<int>> matrix = {
        {0, 0, 1, 1},
        {0, 1, 1, 1},
        {0, 0, 0, 0},
        {0, 0, 1, 1}
    };

    // Step 2: Call the function to find the row with maximum ones
    int result = findRowWithMaxOnesBinarySearch(matrix);

    // Step 3: Print the result
    cout << "Binary Search Approach: Row with maximum 1s is at index " << result << endl;

    return 0;
}