All four approaches in C++
The following are all the four approaches mentioned in the solution in C++,\n\n1. Brute-Force:\n\n\n//Vinayak Kukreja\n//Time Complexity --> n x m matrix --> O(
The following are all the four approaches mentioned in the solution in C++,\n\n**1. Brute-Force:**\n\n```\n//Vinayak Kukreja\n//Time Complexity --> n x m matrix --> O(nm)\n//Space Complexity --> O(1) if we do not consider input provided in the complexity\n\n//Approach #1 --> Brute Force\n//Version --> 1.0\n\nclass Solution {\npublic:\n    bool searchMatrix(vector<vector<int>>& matrix, int target) {\n        int rowLength = matrix.size(); \n        if(rowLength == 0)  //Checking if there are no rows, then false\n            return false;\n        int colLength = matrix[0].size();\n        \n        //Iterating through every value and checking against the target\n        for(int i = 0; i < rowLength; i++)\n            for(int j = 0; j < colLength; j++)\n                if(matrix[i][j] == target)\n                    return true;    //Target Found\n        \n        return false;   //Target Not Found\n    }\n};\n```\n\n**2. Binary-Search:**\n\n```\n//Vinayak Kukreja\n//Time Complexity --> O(lg(n!))\n//Space Complexity --> O(1)\n\n//Approach #2 --> Via Binary Search\n//Version --> 1.0\n\nclass Solution {\npublic:\n    bool searchMatrix(vector<vector<int>>& matrix, int target) {\n        int rowLength = matrix.size();\n        if(rowLength == 0)  //If the number of rows are zero, then returning false\n            return false;\n        int colLength = matrix[0].size();\n        \n        int shorterDimension = min(rowLength, colLength);   //Getting the shorter length between column and row size, it is necessary we take the shorter one or else index out of bound might occur\n        \n        for(int startPos = 0; startPos < shorterDimension; startPos++){\n            //Searching first column slice and then row slice\n            if(binarySearch(matrix, target, startPos, true) || binarySearch(matrix, target, startPos, false))\n                return true;    //Target found\n        }\n        return false;   //Target not found\n    }\n    \n    //Applying binary search to column or row slice of 2D matrix and searching for target\n    bool binarySearch(vector<vector<int>>& matrix, int target, int startingPos, bool rowOrCol){\n        int low = startingPos;  //This position changes via for loop implemented before\n        //Therefore we go in an rotated L-shape kind of flow from left top to right bottom as the start\n        //position increases\n        //  |--------\n        //  | |------\n        //  | | |----\n        int high = rowOrCol ? matrix[0].size()-1 : matrix.size()-1;     //Selecting high value based on searching column or row slice currently, if true then column, if not then row\n              \n        //The following is similar to how binary search works\n        while(low <= high){\n            int mid = (low + high) / 2;     //Calculating middle\n            if(rowOrCol){\n                //If searching columns\n                if(matrix[startingPos][mid] > target)\n                    high = mid - 1;\n                else if(matrix[startingPos][mid] < target)\n                    low = mid + 1;\n                else\n                    return true;\n            }\n            else{\n                //If searching rows\n                if(matrix[mid][startingPos] > target)\n                    high = mid - 1;\n                else if(matrix[mid][startingPos] < target)\n                    low = mid + 1;\n                else\n                    return true;\n            }\n        }\n        return false;   //When target now found in this iteration\n    }\n};\n```\n\n**3. Divide and Conquer:**\n\n*I am unable to solve memory limit error in this. I think the solution should be working in each case and if someone finds the problem with the following, please do let me know, I would update the code. Sorry for the inconvenience,*\n\n```\n//Vinayak Kukreja\n//Time Complexity --> O(nlgn)\n//Space Complexity --> O(lgn)\n\n//Approach #3 --> Divide And Conquer\n//Version --> 1.0\n\nclass Solution {\nprivate:\n    vector<vector<int>> matrixLoc;\n    int targLoc;\n\npublic:\n    bool searchMatrix(vector<vector<int>>& matrix, int target) {\n        //Transfering to local variables for less variables to pass during recursion\n        matrixLoc = matrix;     \n        targLoc = target;\n        \n        if(matrixLoc.size() == 0)   //Checking if no rows present, then returning false\n            return false;\n        \n        //Starting search from top leftmost index to rightmost bottom index\n        return recursiveSearch(0, 0, matrix.size()-1, matrix[0].size()-1);\n    }\n    \n    bool recursiveSearch(int rowLow, int colLow, int rowHigh, int colHigh){\n        \n        //Checking if the matrix is having no height or width\n        if(colLow > colHigh || rowLow > rowHigh)\n            return false;\n        \n        //Checking if the values at extreme ends of given matrix are either bigger or smaller than target, then target would not be present in the matrix\n        else if(matrixLoc[rowLow][colLow] > targLoc || matrixLoc[rowHigh][colHigh] < targLoc)\n            return false;\n        \n        else{\n            int colMid = colLow + (colHigh-colLow)/2;\n        \n            //To find such a row where,\n            //matrixLoc[row-1][colMid] < targetLoc < matrixLoc[row][colMid]\n            int row = rowLow;\n            while(row <=  rowHigh && matrixLoc[row][colMid] <= targLoc){\n                //checking middle column elements against target value\n                if(matrixLoc[row][colMid] == targLoc)   \n                    return true;\n                \n                ++row;\n            }\n            \n            //Recursively now checking the bottom left and top right sub matrices formed\n            return recursiveSearch(row, colLow, rowHigh, colMid-1) || recursiveSearch(rowLow, colMid+1, row-1, colHigh);\n        }\n    }\n};\n```\n\n**4. Search Space Reduction:**\n\n```\n//Vinayak Kukreja\n//Time Complexity --> O(m+n)\n//Space Complexity --> O(1)\n\n//Approach #4 --> Search Space Reduction\n//Version --> 1.0\n\nclass Solution {\npublic:\n    bool searchMatrix(vector<vector<int>>& matrix, int target) {\n        int rowLength = matrix.size();\n        //Checking if there are no rows and hence returning false \n        if(rowLength == 0)\n            return false;\n        int colLength = matrix[0].size();\n        \n        int i = 0, j = colLength - 1;   //Starting from the top-right of the matrix\n        //Moving left if the target is less than the value since column values below would be greater\n        //Moving down if the target is greater than the value because all the values on the left would be smaller\n        while( i < rowLength && j >= 0)\n        {\n            if(matrix[i][j] == target){\n                return true;\n            }\n            else if(matrix[i][j] > target){     //If the current value is greater, then it means the values below this i.e. inside this column would be greater, therefore moving to the left\n                j--;\n            }\n            else{   //Moving down, because all the values would be smaller on the left\n                i++;\n            }\n        }\n        return false;\n    }\n};\n```
['C']