Search in a sorted 2D matrix ( Stored in row major order ) | Php program to find whether a given element is present in the given 2 - D matrix ; Basic binary search to find an element in a 1 - D array ; if element found return true ; if middle less than K then skip the left part of the array else skip the right part ; if not found return false ; Function to search an element in a matrix based on Divide and conquer approach ; if the element lies in the range of this row then call 1 - D binary search on this row ; if the element is less then the starting element of that row then search in upper rows else search in the lower rows ; if not found ; Driver code
< ? php $ M = 3 ; $ N = 4 ; function binarySearch1D ( $ arr , $ K ) { $ low = 0 ; $ high = $ GLOBALS [ ' N ' ] - 1 ; while ( $ low <= $ high ) { $ mid = $ low + ( int ) ( $ high - $ low ) / 2 ; if ( $ arr [ $ mid ] == $ K ) return True ; if ( $ arr [ $ mid ] < $ K ) $ low = $ mid + 1 ; else $ high = $ mid - 1 ; } return False ; } function searchMatrix ( $ matrix , $ K ) { $ low = 0 ; $ high = $ GLOBALS [ ' M ' ] - 1 ; while ( $ low <= $ high ) { $ mid = $ low + ( int ) ( $ high - $ low ) / 2 ; if ( $ K >= $ matrix [ $ mid ] [ 0 ] && $ K <= $ matrix [ $ mid ] [ $ GLOBALS [ ' N ' ] - 1 ] ) return binarySearch1D ( $ matrix [ $ mid ] , $ K ) ; if ( $ K < $ matrix [ $ mid ] [ 0 ] ) $ high = $ mid - 1 ; else $ low = $ mid + 1 ; } return False ; } $ matrix = array ( [ 1 , 3 , 5 , 7 ] , [ 10 , 11 , 16 , 20 ] , [ 23 , 30 , 34 , 50 ] ) ; $ K = 3 ; $ M = 3 ; $ N = 4 ; if ( searchMatrix ( $ matrix , $ K ) ) echo " Found " ; else echo " Not ▁ found " ; ? >