-
Notifications
You must be signed in to change notification settings - Fork 2.3k
/
0074-search-a-2d-matrix.js
75 lines (65 loc) · 2.06 KB
/
0074-search-a-2d-matrix.js
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//////////////////////////////////////////////////////////////////////////////
// Two level Binary search
// Time: O(log(m) + log(n)) Space: O(1)
//////////////////////////////////////////////////////////////////////////////
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function(matrix, target) {
let [rows, cols] = [matrix.length, matrix[0].length];
let [top, bot] = [0, rows-1];
while(top <= bot){
let row = Math.floor((top + bot) / 2);
if(target > matrix[row][cols-1]) {
top = row + 1;
} else if(target < matrix[row][0]) {
bot = row - 1;
} else {
break;
}
}
if(!(top <= bot)) {
return false;
}
let row = Math.floor((top + bot) / 2);
let [l, r] = [0, cols-1];
while(l<=r){
let m = Math.floor((l + r) /2);
if(target > matrix[row][m]) {
l = m +1;
} else if(target < matrix[row][m]) {
r = m - 1;
} else if(target == matrix[row][m]) {
return true;
}
}
return false;
};
//////////////////////////////////////////////////////////////////////////////
// Single Binary Search
// Time: O(log(mn)) Space: O(1)
//////////////////////////////////////////////////////////////////////////////
/**
* @param {number[][]} matrix
* @param {number} target
* Time O(log(ROWS * COLS)) | Space O(1)
* @return {boolean}
*/
var searchMatrix = function (matrix, target) {
const [rows, cols] = [matrix.length, matrix[0].length];
let [left, right] = [0, rows * cols - 1];
while (left <= right) {
const mid = (left + right) >> 1;
const [row, col] = [Math.floor(mid / cols), mid % cols];
const guess = matrix[row][col];
const isTarget = guess === target;
if (isTarget) return true;
const isTargetGreater = guess < target;
if (isTargetGreater) left = mid + 1;
const isTargetLess = target < guess;
if (isTargetLess) right = mid - 1;
}
return false;
};