Search in a sorted 2D matrix ( Stored in row major order ) | Javascript 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
var M = 3 ; var N = 4 ; function binarySearch1D ( arr , K ) { var low = 0 ; var high = N - 1 ; while ( low <= high ) { var mid = low + parseInt ( ( 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 ) { var low = 0 ; var high = M - 1 ; while ( low <= high ) { var mid = low + parseInt ( ( high - low ) / 2 ) ; if ( K >= matrix [ mid ] [ 0 ] && K <= matrix [ mid ] [ N - 1 ] ) return binarySearch1D ( matrix [ mid ] , K ) ; if ( K < matrix [ mid ] [ 0 ] ) high = mid - 1 ; else low = mid + 1 ; } return false ; } var matrix = [ [ 1 , 3 , 5 , 7 ] , [ 10 , 11 , 16 , 20 ] , [ 23 , 30 , 34 , 50 ] ] ; var K = 3 ; if ( searchMatrix ( matrix , K ) ) document . write ( " " ) ; else document . write ( " " ) ;