查找

参考

• 七大查找算法

顺序查找

数组的顺序查找、链表的顺序查找，注意双指针的使用。

递归查找

广度优先搜索

优先遍历当前位置附近的元素

深度优先搜索

优先遍历子节点

二分查找

用于在固定顺序的列表中快速查询

参考 https://labuladong.gitee.io/algo/2/22/61/

二分查找维护查找空间的左、右和中间指示符，并比较查找目标或将查找条件应用于集合的中间值；如果条件不满足或值不相等，则清除目标不可能存在的那一半，并在剩下的一半上继续查找，直到成功为止。如果查以空的一半结束，则无法满足条件，并且无法找到目标。

二分查找主要用于在有序数组中找到目标值，其流程为

• 数组中排在中间的数字 A，与要找的数字比较大小
• 因为数组是有序的，所以：
  • A 较大则说明要查找的数字应该从前半部分查找
  • A 较小则说明应该从查找数字的后半部分查找
• 这样不断查找缩小数量级（扔掉一半数据），直到找完数组为止

function binarySearch(array, target) {
    var low = 0,
        high = array.length - 1

    while (low <= high) {
        var mid = Math.floor(low + ( high - low) / 2);
        if (array[mid] > target)
            high = mid - 1;
        else if (array[mid] < target)
            low = mid + 1;
        else
            return mid;
    }

    return false
}

找到某个数字

题目:704.二分查找

var search = function (nums, target) {
    var l = 0;
    var r = nums.length - 1;
    while (l <= r) {
        var m = l + Math.floor((r - l) / 2); // 等价于(l+r)/2，这么写是为了防止l+r过大溢出
        if (nums[m] === target) {
            return m;
        } else if (nums[m] < target) {
            l = m + 1; // 筛选的范围是[m+1, r]
        } else if (nums[m] > target) {
            r = m - 1; // 筛选的范围是[l, m-1]
        }
    }
    return -1;
};

主要思路是一步步缩小筛选的范围

找到左侧边界

题目:278. 第一个错误的版本

var solution = function(isBadVersion) {
    return function(n) {
        var l = 1
        var r = n
        while(l < r) {
            var m = Math.floor(l + (r-l)/2)
            if(isBadVersion(m)){
                r = m // 缩小右边界，筛选范围[l, m]
            }else {
                l = m +1 // 筛选范围[m+1, r]
            }
        } 
        return l
    };
};

可以抽象成找到左边界（最早错误的那个版本），因此在二分查找找到对应的数字时，还需要向左继续缩小查找范围

来看看更常规的左边界题目：在[1,2,2,2,3,4,5]列表中，找到最早出现2的索引值

右边界

TODO

小结

一定要注意返回值的具体含义

• 使用闭区间搜索，即采用<=判断规则

双指针

• 双指针