二維數組的查找

【題目描述】

在一個二維數組中（每個一維數組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。

思路

1. 思路一：暴力法

暴力解法，既遍歷數組的每一個元素，時間複雜度O(n2)

2.思路二：規律法

利用二維數組由上到下，由左到右遞增的規律，從左下角開始遍歷，如果target元素比當前值小，則往上找，若比當前元素大，則往右找,如果存在，必然找到目標數字。

即選取右上角或者左下角的元素 a[row] [col] 與 target 進行比較， 當target小於元素 a[row] [col] 時，那麼 target 必定在元素 a 所在行的左邊,讓 col-- ；當 target 大於元素 a[row] [col] 時，那麼 target 必定在元素 a 所在列的下邊,讓 row++ ；

時間複雜度O(m+n)

PHP代碼示例

function findElement(array $arr, int $target) {
 if (empty($arr) || empty($target)) {
 return false;
 }
 $row = 0;
 $col = count($arr[0]) - 1;
 while (($row <= count($arr) - 1) && $col >= 0) {
 if ($target == $arr[$row][$col]) {
 return true;
 } else {
 if ($target > $arr[$row][$col]) {
 $row++;
 } else {
 $col--;
 }
 }
 }
 return false;
}

3.思路三：二分法

每一行每一列都按照從左到右遞增的順序排序，把每一行每一列看作有序遞增數組，利用二分查找，通過遍歷每一行查找得到答案，時間複雜度log(n)*log(m)

PHP代碼示例

/**
 * 二分查找
 * @param array $arr
 * @param int $target
 * @param int $low
 * @param int $high
 * @return float
 * @author liu.lei
 */
function binarySearch(Array $arr, int $target, int $low, int $high) {
 while ($low <= $high) {
 $mid = floor(($low + $high) / 2);
 #找到元素
 if ($arr[$mid] == $target) {
 return $mid;
 }
 #中元素比目標大,查找左部
 if ($arr[$mid] > $target) {
 $high = $mid - 1;
 }
 #重元素比目標小,查找右部
 if ($arr[$mid] < $target) {
 $low = $mid + 1;
 }
 }
 //返回小值
 return floor(($low + $high) / 2);
}
/**
 * 遞歸搜索
 * @param array $arr
 * @param int $target
 * @param int $row_start
 * @param int $row_end
 * @param int $col_start
 * @param int $col_end
 * @return bool
 * @author liu.lei
 */
function binarySearchIn2DArray(array $arr, int $target, int $row_start, int $row_end, int $col_start, int $col_end) {
 //查找失敗
 if ($row_start > $row_end || $col_start > $col_end) {
 return false;
 }
 //二分查找,找到中間的行數
 $mid = round(($row_start + $row_end) / 2);
 //找到的值位於x行,result列
 $result = binarySearch($arr[$mid], $target, $col_start, $col_end);
 if ($arr[$mid][$result] == $target) {
 return true;
 }
 //對剩餘的兩部分分別進行遞歸查找
 return (binarySearchIn2DArray($arr, $target, $row_start, $mid - 1, $result + 1, $col_end) || binarySearchIn2DArray($arr, $target, $mid + 1, $row_end, $col_start, $result));
}
/**
 * 二維數組查找元素
 *
 * @param array $arr
 * @param int $target
 * @return bool
 * @author liu.lei
 */
function find(array $arr, int $target) {
 if (empty($arr) || empty($target)) {
 return false;
 }
 //數組的行數
 $row = count($arr) - 1;
 //數組的列數
 $col = count($arr[0]) - 1;
 //如果目標值小於最小值或者目標值大於最大值,那肯定不存在
 if ($target < $arr[0][0] || $target > $arr[$row][$col]) {
 return false;
 }
 return binarySearchIn2DArray($arr, $target, 0, $row, 0, $col);
}
$arr = [
 [1, 2, 3, 4],
 [3, 6, 9, 12],
 [5, 10, 15, 20]
];
$a = find($arr, 10);
var_dump($a);