Binary search in a 2D matrix with explanation.
Hello!\n\nI\'ve just looked through a bunch of solutions and most of them were brute force. \nSo I\'ve decided post a solution with the binary search approach w
Hello!\n\nI\'ve just looked through a bunch of solutions and most of them were brute force. \nSo I\'ve decided post a solution with the binary search approach with explantion.\n\n```\nvar searchMatrix = function(matrix, target) {\n     if(!matrix || !matrix.length) return false;\n    \n    const rows = matrix.length;\n    const cols = matrix[0].length;\n    \n    function hasTarget(startRow, endRow, startCol, endCol) {\n\t\t// recursion base case\n        if(startRow > endRow || startCol > endCol) return false;\n        \n\t\t// find middle of the matrix\n        const middleRow = Math.floor((endRow - startRow) / 2) + startRow;\n        const middleCol = Math.floor((endCol - startCol) / 2) + startCol;\n        \n\t\t// if we found the target we solve the problem, so return true  \n        if(matrix[middleRow][middleCol] === target) return true;\n        \n\t\t// it is the "devide" step, basically, we define the recurrence relation for the recursion function.\n        if (matrix[middleRow][middleCol] < target) {\n\t\t\t// let m - is our middle point.\n\t\t\t// if m less than the target than all points before m also less tha target (marked by x)\n\t\t\t// so we only need look through cells marked by 1 and 2\n\t\t\t// x x x 2 2\n\t\t\t// x x x 2 2\n\t\t\t// x x m 2 2\n\t\t\t// 1 1 1 1 1\n\t\t\t// 1 1 1 1 1\n            return hasTarget(middleRow + 1, endRow, startCol, endCol) ||\n                   hasTarget(startRow, middleRow, middleCol + 1, endCol);\n        } else {\n\t\t\t// let m - is our middle point.\n\t\t\t// if m more than the target than all points after m also bigger than the target (marked by x)\n\t\t\t// so we only need look through cells marked by 1 and 2\n\t\t\t// 1 1 2 2 2\n\t\t\t// 1 1 2 2 2\n\t\t\t// 1 1 m x x\n\t\t\t// 1 1 x x x\n\t\t\t// 1 1 x x x\n            return hasTarget(startRow, endRow, startCol, middleCol - 1) ||\n                   hasTarget(startRow, middleRow - 1, middleCol, endCol);\n        }\n    }\n    \n    return hasTarget(0, rows - 1, 0, cols - 1);\n}\n```\n\nHappy coding!\n
['Recursion', 'Binary Tree', 'JavaScript']