There is a binary matrix (filled only with 0s and 1s), where every row is sorted. An example:

MxN

Mxlog(N)

0,1,1,1,1
0,0,1,1,1
1,1,1,1,1
0,0,0,0,0

0,1,1

0 1 2

lo = 1
hi = 1

mid = 1


Find the row that contains the most ones.

def binarySearch(row):
    lo = 0
    hi = len(row) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if row[mid] == 0:
            lo = mid + 1
        else: # equals 1
            hi = mid - 1

    return lo


def findRow(matrix):
    N = len(matrix[0])
    rowWithMostOnes = 0
    mostOnesInRow = 0

    for index in range(len(matrix)):
        row = matrix[index]

        leftMostOne = binarySearch(row)
        currRowOnes = N - leftMostOne

        if currRowOnes > mostOnesInRow:
            rowWithMostOnes = index
            mostOnesInRow = currRowOnes

    return rowWithMostOnes