Algorithm-二维数组中的查找-BinarySearch

二维数组中的查找

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

最简单的思路

对每行采用二分查找，时间复杂度是O(nlogn)

JavaScript实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// js-binary search-iterative
function binarySearchIterative(a, value)
{
   var mid, lo = 0,
      hi = a.length - 1;
 
  while (lo <= hi) {
    mid = Math.floor((lo + hi) / 2);
 
    if (a[mid] > value) {
      hi = mid - 1;
    } else if (a[mid] < value) {
      lo = mid + 1;
    } else {
      return true;
    }
  }
  return false;
}

function Find(target, array)
{
    let row = array.length;
    let colFirst = new Array();
    for (let i=0; i<row; i++) {
        let result = binarySearchIterative(array[i], target);
        if (result == true)
            return true;
    }
    return false;
}