11、二分查找

11 极客大学-算法训练营-覃超-第十一课.pdf

二分查找前提：

• 目标函数的单调性（单调递增或者递减）==> 可能涉及到数组的排序
• 存在上下界
• 能够通过索引访问

二分查找代码模板

function binarySearch(nums, target){
    let left = 0;
  let right = nums.length-1;
  while(left <= right){
    // let midddle = left + ((right-left)>>1)
      let middle = Math.floor((left+right)/2) 
    if(nums[middle] === target){
            return middle;
    }else if(nums[middle] > target){
            right = middle-1;
    }else if(nums[middle] < target){
            left = middle+1;
    }
  }
  return -1;
}

参考链接

• 二分查找代码模板

• Fast InvSqrt() 扩展阅读

  实战题目

• x 的平方根（字节跳动、微软、亚马逊在半年内面试中考过）

  function mySqry(x){
    if(x<2){return x}
  let left = 1, mid, right = Math.floor(x/2);
  while(left <= right){
      mid = Math.floor(left + (right-left)/2);
    if(mid * mid === x){
        return x;
    }else if(mid * mid > x){
        right = mid - 1;
    }else{
        left = mid + 1;
    }
  }
  return right;
  }

• 有效的完全平方数（亚马逊在半年内面试中考过）

  课后作业

• 搜索旋转排序数组（Facebook、字节跳动、亚马逊在半年内面试常考）

• 搜索二维矩阵（亚马逊、微软、Facebook 在半年内面试中考过）
• 寻找旋转排序数组中的最小值（亚马逊、微软、字节跳动在半年内面试中考过）
• 使用二分查找，寻找一个半有序数组 [4, 5, 6, 7, 0, 1, 2] 中间无序的地方
  说明：同学们可以将自己的思路、代码写在学习总结中

特别好用的二分查找法模板（第 2 版）

https://www.liwei.party/2019/06/17/leetcode-solution-new/search-insert-position/

本周作业

简单：

• 柠檬水找零（亚马逊在半年内面试中考过）
• 买卖股票的最佳时机 II （亚马逊、字节跳动、微软在半年内面试中考过）
• 分发饼干（亚马逊在半年内面试中考过）
• 模拟行走机器人

• 使用二分查找，寻找一个半有序数组 [4, 5, 6, 7, 0, 1, 2] 中间无序的地方
  说明：同学们可以将自己的思路、代码写在第 4 周的学习总结中

  中等：

• [ ] 单词接龙（亚马逊在半年内面试常考）

• 岛屿数量（近半年内，亚马逊在面试中考查此题达到 350 次）
• 扫雷游戏（亚马逊、Facebook 在半年内面试中考过）
• 跳跃游戏 （亚马逊、华为、Facebook 在半年内面试中考过）
• 搜索旋转排序数组（Facebook、字节跳动、亚马逊在半年内面试常考）
• 搜索二维矩阵（亚马逊、微软、Facebook 在半年内面试中考过）

• [ ] 寻找旋转排序数组中的最小值（亚马逊、微软、字节跳动在半年内面试中考过）

  困难

• [ ] 单词接龙 II （微软、亚马逊、Facebook 在半年内面试中考过）

• 跳跃游戏 II （亚马逊、华为、字节跳动在半年内面试中考过）