二分查找

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

代码模板 #

简单题的模板几乎都是统一的,根据题目的条件再灵活调整就可以了,比如 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. 山脉数组的峰顶索引

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

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

题目列表 #

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

167. 两数之和 II - 输入有序数组