[Array] finding a number in 2D array
In a 2-D array (each sub-array has same length) every row is ascending from left to right
every col is ascending from up to down, find a number in this array, return a true/false to indicate found/not found
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| public class Solution {
public boolean Find(int target, int[][] array) {
if (array.length == 0 || array[0].length == 0) return false;
int l = array.length - 1;
int k = array[0].length - 1;
if (target < array[0][0] || target > array[l][k]) return false;
for (int i = 0; i <= l; i++) {
if (array[i][0] > target) continue;
if (search(target, i, 0, k, array)) return true;
}
return false;
}
private boolean search(int target, int i, int min, int max, int[][] arr) {
if (max >= min) {
int mid = min+(max-min) / 2;
if (target == arr[i][mid]) return true;
if (arr[i][mid] > target) {
return search(target, i, min, mid-1, arr);
} else {
return search(target, i, mid+1, max, arr);
}
}
return false;
}
}
|
simplest solution, to traverse trough the first col of array in $m$ time and run a binary search for each row. total time complexity is $mlogn$.