Cracking the coding interview 9.6 Given a matrix in which each row and each column is sorted. write a method to find an element in it. 實現一個函數，在一個行列都排序的二維數組中查找某個元素是否存在。 思路：如果待搜索元素小於一行中最左邊的元素或者大於一行中最右面的元素，那麼待查找元素不可能存在於當前行中。列也同理。從上下左右四個方向，從外向內分別判斷待查找元素是否可能存在於其中。逐步縮小搜索范圍。 [cpp] /** * Search specific value in sorted 2D array, which both row and column are sorted in ascending order. * * arr: address of a array, row-major order stored * nRow: row of input array * nColumn: column of input array * nVal: the value that to be searched */ bool SearchSorted2D(int *arr, const int nRow, const int nColumn, const int nVal) { int nTop = 0; int nBottom = nRow - 1; int nLeft = 0; int nRight = nColumn - 1; while ((nTop <= nBottom) && (nLeft <= nRight)) { // Compare with the most top-left(smallest) and the most bottom-right(biggest) element. if (nVal < (*(arr+nColumn*nTop+nLeft)) || (nVal > (*(arr+nColumn*nBottom+nRight)))) return false; if (*(arr+nColumn*nTop+nRight) == nVal) { printf("arr[%d][%d]=%d\n", nTop, nRight, *(arr+nColumn*nTop+nRight)); return true; } if (*(arr+nColumn*nBottom+nLeft) == nVal) { printf("arr[%d][%d]=%d\n", nBottom, nLeft, *(arr+nColumn*nBottom+nLeft)); return true; } if ((nTop == nBottom) && (nLeft == nRight)) return false; ////////////////////////////////// // Search from top-right corner // the most right element of row is smaller than nVal, then the whole row is smaller than nVal if (*(arr+nColumn*nTop+nRight) < nVal) nTop ++; // the most top element of column is bigger than nVal, then the whole column is smaller than nVal if (*(arr+nColumn*nTop+nRight) > nVal) nRight --; ////////////////////////////////// // Search from bottom-left corner // the most bottom element of column is smaller than nVal, then the whole column is smaller than nVal if (*(arr+nColumn*nBottom+nLeft) < nVal) nLeft ++; // the most left element of row is smaller than nVal, then the whole row is smaller than nVal if (*(arr+nColumn*nBottom+nLeft) > nVal) nBottom --; } return false; }
