6.15二维数组中的查找 - WisperDin/blog GitHub Wiki

描述

面试题4：二维数组中的查找 题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路

其实这题是一个 二分查找 的变式，可以利用二分查找的思想快速排除有序序列中的不符合要求的元素，通过观察可知，将二维数组看成一个矩阵，从左往右递增，从上到下递增，可以从二维数组的右上角（第一行，最后一列 组成的一个递增序列）开始 此时序列的中点即右上角的元素，将此元素与查找元素比较

• 相同 查找成功
• 查找元素比右上角元素小 （后半段序列排除，即排除最后一列）
• 查找元素比右上角元素大 (前半段序列排除，即排除第一行)

排除后的矩阵继续按此方法查找，当查找将要越界时退出循环，查找失败

第一行，最后一列组成的7字形序列，其中必定以顶角10为中点
1,2,7,10,11,13,17

		{1,2,7,10},
		{3,4,10,11},
		{4,5,12,13},
		{6,7,16,17},

代码

func Find(arr [][]int,target int)bool{
	if len(arr)<=0 || len(arr[0])<=0 {
		return false
	}
	//行
	row := 0
	//列
	col := len(arr[0])-1
	for row<len(arr[0]) && col>=0 {
		rightEle := arr[row][col]
		if rightEle == target {
			return true
		}
		if rightEle < target{
			row++
		}else {
			col--
		}
	}
	return false
}