C++ Online Compiler
Example: BinarySearchMaxOnesRow in C++
C
C++
C#
Java
Python
PHP
main.cpp
STDIN
Run
// 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; }
Output
Clear
ADVERTISEMENTS