Search a 2D Matrix @leetcode

SearchMatrix.java

package leetcode.binarySearch;

/**
 * Solution: BinarySearch. it will be a sorted array if matrix expand line by line.
 * The problem is to handle the position and element value in matrix.
 * Only first and last element could be reached in last two situation.
 * element = matrix[0][0]; element = matrix[matrix.length - 1][matrix[0].length - 1]; also works but not beautiful.
 * 
 * @author jeffwan
 * @date Mar 9, 2014	
 */
public class SearchMatrix {
	public boolean searchMatrix(int[][] matrix, int target) {
		if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
			return false;
		}	

		int start, end, mid, m, n, element;
		m = matrix.length;
		n = matrix[0].length;
		start = 0;
		end = m * n - 1;

		while (start + 1 < end) {
			mid = start + (end - start) / 2;
			element = matrix[mid / n][ mid % n];
			
			if (target == element) {
				return true;
			} else if (target < element) {
				end = mid;
			} else {
				start = mid;
			}
		}
		
		
		element = matrix[start / n][ start % n];
		if (target == element) {
			return true;
		}
		
		element = matrix[end / n][ end % n];
		if (target == element) {
			return true;
		}

		return false;
	}

	// Solution2: BinarySearch line first, and then search column. Use two time BinarySearch -- low efficiency.
	public boolean searchMatrix2(int[][]A, int target) {
		
		if(A == null || A.length == 0) {
			return false;
		}
		
		int start, end, mid;
		int flag;
		
		// 1. search target number line
		start = 0;
		end = A.length - 1;
		while (start + 1 < end) {
			mid = start + (end - start) / 2;
			if (target == A[mid][0]) {
				return true;
			} else if (target < A[mid][0]) {
				end = mid;
			} else {
				start = mid;
			}
		}
		
		if (target == A[start][0]) {
			return true;
		} else if (target == A[end][0]) {
			return true;
		} else  if (target > A[start][0] && target < A[end][0]){
			flag = start;
		} else {
			flag = end;
		}
		
		
		// 2. search target number column
		start = 0;
		end = A[flag].length - 1;
		while (start + 1 < end) {
			mid = start + (end - start) / 2;
			if (target == A[flag][mid]) {
				return true;
			} else if (target < A[flag][mid]) {
				end = mid;
			} else {
				start = mid;
			}
		}
		
		
		if (target == A[flag][end]) {
			return true;
		}
		
		return false;
	}
}