package com.algorithms.search.binary;

/**
 * LeetCode 74. Search a 2D Matrix
 *
 * Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
 * Integers in each row are sorted from left to right.
 * The first integer of each row is greater than the last integer of the previous row.
 *
 * For example, Consider the following matrix:
 *  [
 *    [1,   3,  5,  7],
 *    [10, 11, 16, 20],
 *    [23, 30, 34, 50]
 *  ]
 *  Given target = 3, return true.
 */
public class Search2DMatrix {

    public static boolean searchMatrix(int[][] matrix, int target) {

    }

    public static void main(String[] args) {

    }
}

@@ -632,65 +632,1151 @@
  %7B%0D%0A
-%0D%0A    %7D%0D%0A%0D%0A    public static void main(String%5B%5D args) %7B%0D%0A
+        if (matrix == null %7C%7C matrix.length == 0) %7B%0D%0A            return false;%0D%0A        %7D%0D%0A        int hIndex = matrix%5B0%5D.length - 1;%0D%0A%0D%0A        int low = 0;%0D%0A        int high = matrix.length - 1;%0D%0A        int start = 0;%0D%0A        int end = matrix%5B0%5D.length - 1;%0D%0A%0D%0A        while (start %3C= end && low %3C= high) %7B%0D%0A            int mid = start + (end - start) / 2;%0D%0A            int med = low + (high - low) / 2;%0D%0A            if (matrix%5Bmed%5D%5Bmid%5D == target) %7B%0D%0A                return true;%0D%0A%0D%0A            %7D else if (matrix%5Bmed%5D%5Bmid%5D %3C target) %7B%0D%0A                if (matrix%5Bmed%5D%5BhIndex%5D == target) %7B%0D%0A                    return true;%0D%0A%0D%0A                %7D else if (matrix%5Bmed%5D%5BhIndex%5D %3E target) %7B%0D%0A                    start = mid + 1;%0D%0A%0D%0A                %7D else %7B%0D%0A                    low = med + 1;%0D%0A                %7D%0D%0A%0D%0A            %7D else %7B%0D%0A                if (matrix%5Bmed%5D%5B0%5D == target) %7B%0D%0A                    return true;%0D%0A%0D%0A                %7D else if (matrix%5Bmed%5D%5B0%5D %3C target) %7B%0D%0A                    end = mid - 1;%0D%0A%0D%0A                %7D else %7B%0D%0A                    high = med - 1;%0D%0A                %7D%0D%0A            %7D%0D%0A        %7D%0D%0A        return false;
 %0D%0A  

add search 2d matrix