Counting 1's in a n x n array of 0's and 1's
Since all 1's come before the 0's, you can find the index of the first 0 using Binary search algorithm (which is log N) and you just have to do this for all the N rows. So the total complexity is NlogN.
Assuming that in each row of the array, all 1's come before the 0's, how would I be able to come up with an (O)nlogn algorithm to count the 1's in the array. I think first I would have to make a counter, search each row for 1's (n), and add that to the counter. Where does the "log n part" come into play? I read that a recursive algorithm to do this has nlogn complexity, but Im not too sure how I would do this. I know how to do this in O(n^2) with for loops. Pseudo code or hints would be helpful! Thank you