Commit75193fd

authored

Merge pull requestneetcode-gh#1265 from Abusagit/main

Update search_a_2d_matrix.cpp

2 parentsd6804d9 +32e2ea6 commit75193fdCopy full SHA for 75193fd

File tree

+38

-0

lines changed

+38

-0

lines changed

Lines changed: 38 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -47,3 +47,41 @@ class Solution {`
`47`	`47`	`returnfalse;`
`48`	`48`	`}`
`49`	`49`	`};`
	`50`	`+`
	`51`	`+// Same approach with implicit array linearization`
	`52`	`+// T(n) = O(log_2(mn)) = O(log_2(m) + log_2(n))`
	`53`	`+classSolution {`
	`54`	`+public:`
	`55`	`+boolsearchMatrix(vector<vector<int>>& matrix,int target) {`
	`56`	`+`
	`57`	`+int left =0;`
	`58`	`+int m = matrix.size();`
	`59`	`+int n = matrix[0].size();`
	`60`	`+int right = m * n -1;`
	`61`	`+`
	`62`	`+while (left <= right){`
	`63`	`+`
	`64`	`+int middle = right + (left - right) /2;`
	`65`	`+`
	`66`	`+// compute sub-indices using matrix structure`
	`67`	`+int row = middle / n;`
	`68`	`+int col = middle % n;`
	`69`	`+`
	`70`	`+`
	`71`	`+//ordinary binary search`
	`72`	`+int middle_x = matrix[row][col];`
	`73`	`+if (target > middle_x){`
	`74`	`+ left = ++middle;`
	`75`	`+ }elseif (target < middle_x){`
	`76`	`+ right = --middle;`
	`77`	`+ }else {`
	`78`	`+returntrue;`
	`79`	`+ }`
	`80`	`+`
	`81`	`+`
	`82`	`+ }`
	`83`	`+`
	`84`	`+returnfalse;`
	`85`	`+`
	`86`	`+ }`
	`87`	`+};`

Comments

(0)