二分查找

二分查找利用已经排好序的数组,每次查找可以将查找范围减半,查找范围内只剩一个数据时查找结束。

代码模板 #

简单题的模板几乎都是统一的,根据题目的条件再灵活调整就可以了,比如 704. 二分查找

var search = function(nums, target) {
    let low = 0, high = nums.length - 1;
    while (low <= high) {
        const mid = Math.floor((high - low) / 2) + low;
        const num = nums[mid];
        if (num === target) {
            return mid;
        } else if (num > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
};

其它几乎同样模版的题目:

374. 猜数字大小

35. 搜索插入位置

852. 山脉数组的峰顶索引

如果要查找两数之和而不是直接的 target,稍微复杂一点比如 167. 两数之和 II - 输入有序数组

var twoSum = function(numbers, target) {
    for (let i = 0; i < numbers.length; i++) {
        let low = i + 1
        let high = numbers.length - 1
        while (low <= high) {
            let mid = Math.floor((high - low) / 2) + low
            if (numbers[mid] + numbers[i] == target) {
                return [i+1, mid+1]
            } else if (numbers[mid]+numbers[i] > target) {
                high = mid - 1
            } else {
                low = mid + 1
            }
        }
    }
    return [-1, -1]
};

归纳起来上面几个问题要注意的就是:

  1. 初始值设置
  2. 循环的终止条件
  3. 返回值

题目列表 #

专题列表 https://leetcode.cn/study-plan/binary-search/

本文共 356 字,上次修改于 Aug 1, 2022
相关标签: 算法