Commite40ba90

authored

Merge pull requestneetcode-gh#1011 from ritesh-dt/main

Add solution for 74 - Search a 2D Matrix in C

2 parents93d844c +4f8082e commite40ba90Copy full SHA for e40ba90

File tree

+47

-0

lines changed

+47

-0

lines changed

Lines changed: 47 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,47 @@`
	`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`	`+boolsearchMatrix(int*matrix,intmatrixSize,intmatrixColSize,inttarget){`
	`22`	`+intm=matrixSize;`
	`23`	`+intn=*matrixColSize;`
	`24`	`+`
	`25`	`+intlow=0;`
	`26`	`+inthigh=m*n-1;`
	`27`	`+`
	`28`	`+intmid=low+ (high-low)/2;`
	`29`	`+`
	`30`	`+`
	`31`	`+while (low <=high) {`
	`32`	`+introw=mid /n;`
	`33`	`+intcol=mid %n;`
	`34`	`+`
	`35`	`+if (matrix[row][col]>target)`
	`36`	`+high=mid-1;`
	`37`	`+elseif (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`	`+}`

Comments

(0)