面試題21: 二維數組搜尋

題目: 設計一個算法對 m*n 矩陣進行搜尋,這個矩陣擁有如下屬性.

    1)每行的數都是從左到右排序好的.

    2)每行的首數大于上行的尾數.

其實這題就是用二分查找算法,二分查找一般是在一維數組上進行搜尋,解決這道題的關鍵就是如何将二維數組映射成一維數組.

映射關系為: k=i*n+j,j<n,k為在一維數組的中的下标值,i,j分别為二維數組中的行和列.根據前面的可以推導出i=k/n,j=k%n.

代碼實作:

package main

import "fmt"

const M  = 3
const N  = 3
func searchMatrix(matrix interface{}, target int) bool {
	a, m, n := matrix.([M][N]int), M, N
	low, high, mid := 0, m * n -1, 0

	for low < high {
		mid = (low + high) / 2
		if a[mid / n][mid % n] == target {
			return true
		} else if a[mid / n][mid % n] < target {
			low = mid + 1
		} else {
			high = mid - 1
		}
	}
	return false
}

func main() {
	r := searchMatrix([M][N]int{{1,2,3},{4,5,6},{7,8,9}}, 3)
	fmt.Println(r)
}