博文视点算法题目解答

到了2012年，才发现自己iteye的账号里躺着几个可怜的邮件。原来是些算法题，真帅。
看了下，感觉很简单嘛。就想把题目的答案写封邮件过去，抬头一看，还有时效的。
算了，虽然已错过了时间，不过还是可以把自己的思路记录一下。以供以后咨询。

题目1：

二维数组中的查找

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7，则返回true；如果查找数字5，由于数组不含有该数字，则返回false。

(alt+p)


(alt+i)


解答。

其实这个题目不算很难。 关键是如何寻找。
最笨的方法是，扫一遍所有的数据就好了。
可是题目已经告诉我们这个是有序的。
那个根据这个有序性，我们是不是可以做些什么事情来进行优化呢？
第一个想法是这样的：
先扫描第一行，如果遇到第一个大于目标值的数字停下（假定，这时没有搜索到目标值），那么可以记录下当前的index， 然后在搜索第二行的时候，就不需要到这个位置，最多到index-1就好了。
然后递归就好了。
这个最差情况下，还是要扫描一般的数据， 实际上复杂度并没有降低多少。

在第一个想法的基础上，
进行如下改进：
1） 第一行的搜索，使用二分查找。
2）第二行的搜索，并不用从头开始，而是从第一行第一个大于目标值的数字的左下角的数字开始向前搜索。
如果等于目标值就停止。
如果大于目标值，就向前搜索，直到找到一个小于目标值的数字。
如果小于目标值，直接转入到下一行数字。
这样做的好处是，
1， 充分利用了 右边的数字比左边大的好处。
2. 充分利用了 下面的数字比上面的大。
可以尽可能的减少搜索方向和次数。

伪码如下：
 index = 0 // pointer
 // locate first row.
 for element in row:
       if element < targetValue :
              index++
       if element == targetValue:
              return True

 // other rows
 for rows in arrays:
       rowsId=1
       while True:
          row = rows[rowsId]
          // locate last number less than targetValue
          if row[index] > targetValue:
                 index--;
          if row[index] == targetValue:
                 return True
          if row[index] < targetValue:
                 rowsId++
          if index < 0:
                  return False

// Finished