First Column Number That Has One Occurs

题目地址：
http://www.1point3acres.com/bbs/thread-291233-1-1.html

题目：
 Given a 2D array. Each row is constructed by 0's at the beginning and 1's at the following.
ex: [
       [0,0,0,0,0,1,1]
       [0,0,0,1,1,1,1]
       [0,0,0,0,1,1,1]
      ]
Return the first column number that has 1 occurs. In the example it should be 3/

解题思路：
这道题就是二分查找法。

代码：

public class FirstColumnNumberThatHasOneOccurs {

    public int find(int[][] matrix){
        // assuming that the row and col of the matrix is larger than 0        int row = matrix.length;
        int col = matrix[0].length;
        int start = 0;
        int end = col - 1;
        while(start + 1 < end){
            int mid = start + (end - start) / 2;
            int count = getCount(matrix, row, mid);
            if(count == 0){
                start = mid;
            }
            else{
                end = mid;
            }
        }
        int startCount = getCount(matrix, row, start);
        int endCount = getCount(matrix, row, end);
        return startCount != 0 ? start : end;
    }

    private int getCount(int[][] matrix, int row, int mid) {
        int rst = 0;
        for(int i = 0; i <= row - 1; i++){
            rst += matrix[i][mid] == 1 ? 1 : 0;
        }
        return rst;
    }

    public static void main(String[] args){
        FirstColumnNumberThatHasOneOccurs firstColumnNumberThatHasOneOccurs = new FirstColumnNumberThatHasOneOccurs();
        int[][] matrix = {{0, 0, 0, 0, 0, 1, 1}, {0, 0, 0, 1, 1, 1, 1}, {0, 0, 0, 0, 1, 1, 1}};
        int rst = firstColumnNumberThatHasOneOccurs.find(matrix);
        System.out.println(rst);
    }

}