Leftmost Column with atleast one 1 in a row | C ++ implementation to find the Leftmost Column with atleast a 1 in a sorted binary matrix ; Function to search for the leftmost column of the matrix with atleast a 1 in sorted binary matrix ; Loop to iterate over all the rows of the matrix ; Binary Search to find the leftmost occurence of the 1 ; Condition if the column contains the 1 at this position of matrix ; If there is a better solution then update the answer ; Condition if the solution doesn 't exist in the matrix ; Driver Code
#include <bits/stdc++.h> NEW_LINE #define N  3 NEW_LINE using namespace std ; int search ( int mat [ ] [ 3 ] , int n , int m ) { int i , a = INT_MAX ; for ( i = 0 ; i < n ; i ++ ) { int low = 0 ; int high = m - 1 ; int mid ; int ans = INT_MAX ; while ( low <= high ) { mid = ( low + high ) / 2 ; if ( mat [ i ] [ mid ] == 1 ) { if ( mid == 0 ) { ans = 0 ; break ; } else if ( mat [ i ] [ mid - 1 ] == 0 ) { ans = mid ; break ; } } if ( mat [ i ] [ mid ] == 1 ) high = mid - 1 ; else low = mid + 1 ; } if ( ans < a ) a = ans ; } if ( a == INT_MAX ) return -1 ; return a + 1 ; } int main ( ) { int mat [ 3 ] [ 3 ] = { 0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 1 } ; cout << search ( mat , 3 , 3 ) ; return 0 ; }