1+ /*
2+ Given a 2d matrix, where,
3+ 1. the rows are sorted from left to right,
4+ 2. the last element of each row is less than first element of next row
5+
6+ Find an efficient method to search for a given element in this array
7+ Ex. matrix = [[ 1, 3, 5, 7],
8+ [10, 11, 16, 20],
9+ [23, 30, 34, 60]],
10+ target = 3 -> true (3 exists)
11+
12+ The 2D matrix can be thought of as a 1D array if the rows are arranged
13+ sequentially. And given the conditions, the 1D array will also be sorted.
14+ So, binary search can be used to solve this problem with indexes (row, col)
15+ rather than one.
16+
17+ Time: O(log(mn))
18+ Space: O(1)
19+ */
20+
21+ bool searchMatrix (int * * matrix ,int matrixSize ,int * matrixColSize ,int target ){
22+ int m = matrixSize ;
23+ int n = * matrixColSize ;
24+
25+ int low = 0 ;
26+ int high = m * n - 1 ;
27+
28+ int mid = low + (high - low )/2 ;
29+
30+
31+ while (low <=high ) {
32+ int row = mid /n ;
33+ int col = mid %n ;
34+
35+ if (matrix [row ][col ]> target )
36+ high = mid - 1 ;
37+ else if (matrix [row ][col ]< target )
38+ low = mid + 1 ;
39+ else
40+ return true;
41+ mid = low + (high - low )/2 ;
42+
43+ }
44+
45+ return false;
46+
47+ }