javascript 二分法查找二维递增数组

var totalArr = [
    [1, 3, 43, 55, 65],
    [76, 87, 97, 123, 125],
    [134, 146, 168, 456, 652]
];

假设有数组 totalArr ，每项的值都是递增的，后一个数组比前一个数组的值都大，现在希望在 totalArr 数组中查找是否存在其中一个某个值：

function find(arr, number) {
    for (var i = 0; i < arr.length; i++) {
        var lastValue = arr[i][arr[i].length - 1];
        if (lastValue == number) {
            return true;
        }else if(lastValue > number) { // 范围在当前数组内
            return halfCut(arr[i], number);
        }
    }
    return false;
}
function halfCut(arr, number) {
    if (arr.length == 1) {
        return arr[0] == number;
    }
    var midIndex = Math.floor(arr.length / 2);
    var midValue = arr[midIndex];
    if (midValue == number) {
        return true;
    }else if (number < midValue) {
        return halfCut(arr.slice(0, midIndex), number);
    }else{
        return halfCut(arr.slice(midIndex+1, arr.length), number);
    }
}

调用 find(totalArr, 66) ，返回 false，调用 find(totalArr, 146)，返回 true。

1. 首先 find 通过循环数组每一次，用数组最后的值与 number 值做比较，如果相等，直接返回 true，否则判断 number 是否比最后一个值大，如果大则循环下一层继续比较，如果小，则把该层数组和 number 传给 halfCut 方法。
2. halfCut 首先跳过长度是否为 1 的判断，获取数组中间值，如果中间值与 number 相等，直接返回 true，否则，如果 number 小于中间值，则用前半段再次调用 halfCut，直到剩下一个元素，比较是否与 number 相等，不相等则可以肯定该数不在本数组中存在。