二分法

704. 二分查找

704. 二分查找 - 力扣（Leetcode）

有序数组中查询目标值，数组中无重复元素

对于二分个人感觉难点就是在于边界条件的判断，就好比while(l < r)还是while(l <= r)，还有r = m还是r = m - 1，这是一直搞混的。

一般写二分区间定义就是俩种，左闭右闭[l, r]，左闭右开[l, r)

左闭右闭

• while(l <= r)，因为l === r的时候也有意义
• if(nums[m] > target) r = m - 1;，因为此时的nums[m]一定不是 target，[ l , m - 1]

var search = function (nums, target) {
  let l = 0
  let r = nums.length - 1 // 可以取到最后一位
  while (l <= r) {
    // 左闭右闭
    const m = Math.floor((l + r) / 2)
    // 防止溢出
    // const m = Math.floor(l + (r - l) / 2);
    if (nums[m] === target) return m
    else if (nums[m] > target) r = m - 1
    else l = m + 1
  }
  return -1
}

左闭右开

• while(l < r)，因为取不到 r
• if(nums[m] > target) r = m;，因为 nums[m]不是 target，[ l , m )

var search = function (nums, target) {
  let l = 0
  let r = nums.length // 取不到r
  while (l < r) {
    // 左闭右开
    const m = Math.floor((l + r) / 2)
    if (nums[m] === target) return m
    else if (nums[m] > target) r = m
    else l = m + 1
  }
  return -1
}

69. x 的平方根

这一题就容易卡死循环，就比如 8 的平方根是 2.6 左右，答案是 2，l 和 r 不会相等，所以得在最后加一个判断

var mySqrt = function (x) {
  if (x <= 1) return x
  let l = 0
  let r = x / 2 + 1 // 也可以用x
  while (l <= r) {
    // 取得到r
    const m = Math.floor((l + r) / 2)
    if (m * m === x) return m
    else if (m * m > x) r = m
    else l = m
    if (m === Math.floor((l + r) / 2)) return m
  }
}

35. 搜索插入位置

也是二分查找，如果没有查询到也需要返回一个值，没查到其实就是返回 left 的值

var searchInsert = function (nums, target) {
  let l = 0
  let r = nums.length
  while (l < r) {
    let m = Math.floor((l + r) / 2)
    if (nums[m] === target) return m
    else if (nums[m] > target) r = m
    else l = m + 1
  }
  return l
}

367. 有效的完全平方数

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false

这一题和 x 的平方根基本一致

var isPerfectSquare = function (num) {
  if (num <= 0) return true
  let l = 0
  let r = num / 2 + 1
  while (l <= r) {
    let m = Math.floor((l + r) / 2)
    if (m * m === num) return true
    else if (m * m > num) r = m
    else l = m + 1
    // 防止死循环
    if (m === Math.floor((l + r) / 2)) return false
  }
}

相关题目推荐

• 300. 最长上升子序列
• 718. 最长重复子数组
• 349. 两个数组的交集
• 230. 二叉搜索树中第 K 小的元素
• 4. 寻找两个正序数组的中位数
• 153. 寻找旋转排序数组中的最小值
• 162. 寻找峰值
• 34. 在排序数组中查找元素的第一个和最后一个位置
• 240. 搜索二维矩阵 II
• 887. 鸡蛋掉落
• 222. 完全二叉树的节点个数
• 33. 搜索旋转排序数组
• 面试题 10.03. 搜索旋转数组
• 50. Pow(x, n)
• 剑指 Offer 11. 旋转数组的最小数字

导出上面链接用的小工具函数

codetop 直接超链接导出成 md 格式：

let links = document.querySelectorAll('.external-link')
console.log(links)

let res = ''
for (let link of links) {
  res += '- ' + `[${link.innerHTML}]` + `(${link.href})` + '\n'
}

console.log(res)