• Home
  • home > theory > algorithm > Sorting >

    数组二分查找到二分法的感悟笔记

    Author：zhoulujun Date：

    在 D 天内送达包裹的能力,爱吃香蕉的珂珂 都可以用二分查找去解决，闭区间的循环条件是 while (left

    二分查找是一只思维模式，最简单就是：https://leetcode.cn/problems/binary-search/description/

    这个题目之前也会写，但是看了 

    二分查找（Binary Search）也叫作折半查找，前提是查找的顺序结构是有序的，我们一般在数组上进行二分查找。

    二分查找就好像猜数字大小游戏一样。假设要数字目标值属于 [1, 1000] 范围内，当我们猜的数字小于这个目标值时（"Too low"），我们需要往大去猜；反之大于这个目标值时（"Too high"），我们需要往小去猜。当然这里猜的方式并不是盲目的，我们每次都取中间值去猜，每猜一次可以缩小当前一半的范围，这样可以大大提高效率。二分查找本质上也是这样的过程，时间复杂度为 O(logn) ，在较大数据情况下相比线性查找要快非常多。

    1. 定义一个左指针 left 标记当前查找区间的左边界，一个右指针 right 标记当前查找范围的右边界。

    2. 每次取 mid 来判断当前取的值是否等于目标值 target。

      1. 如果等于 target 就直接返回 mid ；

      2. 如果小于目标值 target ，那么将左边界变为 mid + 1，缩小区间范围继续在 [mid + 1, right] 范围内进行二分查找

      3. 如果大于目标值 target ，那么将右边界变为 mid - 1，缩小区间范围继续在 [left, mid - 1] 范围内进行二分查找。

    3. 最后出现了 left > right 的情况，说明区间范围大小缩小到 0 都无法找到该目标值，那么很明显数组中不存在这个目标值 target，此时退出循环，返回 -1 。

    例如在数组：1,2,3,4,7,9,10中查找元素2，如图所示：

    704.二分查找

    开闭区间：

    在二分查找法中，开区间和闭区间在写法上只有一个区别：

    • 闭区间的循环条件是 while (left <= right)。

    • 开区间的循环条件是 while (left < right)

    开区间和闭区间的区别在于是否包含边界值。比如区间只有 [left, right]，即：left<=target<=right

     [left, right] ,[left, right]) ,(left, right])],(left, right]) 

    • [left, right] 表示包含left和right的闭区间。

    • [left, right) 表示包含left但不包含right的开区间。

    • (left, right] 表示不包含left但包含right的开区间。

    • (left, right) 表示不包含left也不包含right的开区间。


    闭区区间核心代码是：

    if (nums[middle] > target) {
  right = middle - 1; // target 在左区间，所以[left, middle - 1]
} else if (nums[middle] < target) {
  left = middle + 1; // target 在右区间，所以[middle + 1, right]
} else { // nums[middle] == target
  return middle; // 数组中找到目标值，直接返回下标
}

    之很容易搞混 ，

    1. 如果目标值等于中间元素，那么我们找到了目标值，可以直接返回结果。

    2. 如果目标值大于中间元素，那么我们可以排除掉左半部分，因为左半部分的所有元素都小于中间元素，而目标值大于中间元素。因此，我们将搜索范围更新为右半部分，即将 left 更新为 mid + 1。

    3. 如果目标值小于中间元素，那么我们可以排除掉右半部分，因为右半部分的所有元素都大于中间元素，而目标值小于中间元素。因此，我们将搜索范围更新为左半部分，即将 right 更新为 mid - 1。

    在每次迭代中缩小搜索范围，直到找到目标值或搜索范围为空。


    左闭右闭、左开右闭，都可以是这个写法

    左闭右开、左开右开得换一下

    左闭右开代码

    var search = function(nums, target) {
  let mid, left = 0, right = nums.length - 1;
  // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
  while (left< right) {
    // 位运算 + 防止大数溢出
    mid = Math.floor((left+right)/2);
    // 如果中间数大于目标值，要把中间数排除查找范围，所以右边界更新为mid；如果右边界更新为mid-1，那中间数还在下次查找范围内
    if (nums[mid] > target) {
      right = mid;  // 去左面闭区间寻找， target 在左区间，在[left, middle)中
    } else if (nums[mid]< target) {
      left = mid + 1;   // 去右面闭区间寻找
    } else {
      return mid;
    }
  }
  return -1;
};

    理论上，在所有情况下使用 right = mid + 1 都是可以的。但是，在左闭右开区间中，使用 right = mid + 1 会导致效率降低。

    • 在右闭区间中，目标值可能等于right。因此，需要将right更新为mid的下一个位置，以确保目标值在下次查找中不会被排除。

    • 在右开区间中，目标值不可能等于right。因此，将right更新为mid即可。

    总结：只要右闭，就是right =mid+1，否则right = mid

    递归写法

    function binarySearch(nums, target, left, right) {
  if (left > right) {
    return -1;
  }

  const mid = left + Math.floor((right - left) / 2);

  if (nums[mid] === target) {
    return mid;
  } else if (nums[mid]< target) {
    return binarySearch(nums, target, mid + 1, right);
  } else {
    return binarySearch(nums, target, left, mid - 1);
  }
}
// 使用示例
const nums = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const target = 5;
const index = binarySearch(nums, target, 0, nums.length - 1);

    递归看起来更好理解写。


    二分查找考题：

    运包裹

    https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/description/ 

    function test(weights, days) {
  // 最小装载能力就是数组的最大值（因为包裹不能拆分呀）
  let left = weights[weights.length-1];
  // 最大装载能力就是数组的总和（极限情况，一次性装完）
  let right = weights.reduce((a, b) => a + b, 0);
  // 然后从开始二分查找
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    let day = 1;
    let cur = 0;
    for (let weight of weights) {
      //如果当前重量加上当前物品重量大于中间值，天数加1，当前重量重置为0
      if (cur + weight > mid) {
        day += 1;
        cur = 0;
      }
      // 将当前物品重量加到当前重量
      cur += weight;
    }
    // 如果装载的天数少于实际天数，说明装载量大量，可以缩小装载量(指针右移），因为是右闭，所以是<=
    if (day <= days) {
      right = mid;
    } else {
      left = mid + 1;// 否则加大装载
    }
  }
  return left;
}

console.log(test([3, 2, 2, 4, 1, 4], 3));


    分段计费

    一遍面试不会考这么简单，比如分段收费（营销措施，买的越多，越便宜）

    const config = [
  { range: [1, 5], fee: 30 },
  { range: [5, 10], fee: 20 },
  { range: [10, 30], fee: 15 },
  { range: [30, 60], fee: 10 },
  { range: [60, 120], fee: 5 },
  { range: [120, Infinity], fee: 1 },
];
function calculate(num){
  // 缓存迭代结果
  let count = 0;
  let total = 0;
  for(const {range:[min,max],fee} of config ){
    // 已经循环过的，直接推出
    if(num<min){
      break;
    }
    // 当前值不在区间范围，缓存，继续查找
    if(num>max){
      count = (max-min)*fee;
    }
    if(min<num&&num<max){
      if(count===0){
        total = num*fee;
      }else {
        total = count + (num-min)*fee;
      }
      break;
    }
  }
}
// 上面的代码每次都要变量一遍，太耗费时间, 可以以空间换时间的
let count =0;
const cache = [0]
const temp = config.slice()
temp.pop();
temp.forEach(({range:[min,max],fee},index)=>{
  count+=(max-min)*fee
  cache.push(count)
})
console.log(cache)
function calculate2(num){

  let left = 0;
  let right = config.length -1;
  let total;
  while (left<=right){
    const mid = Math.floor((left+right)/2);
    const {range:[min,max],fee} = config[mid];
    if(min<num&&num<max){
      const cacheFee  = cache[mid];
      if(mid===0){
        total = num*fee;
      }else {
        total = cacheFee+(num-min)*fee;
      }
      break;
    }
    if(num>max){
      left = mid+1
    }
    if(num<min){
      right = mid-1;
    }
    console.log(mid)
  }
  return total;
}
console.log(calculate2(6))


    二分查找，其实就是双指针，更多关于双指针的，推举阅读 《双指针相关问题(滑动窗口/反转字符串/回文字串)总结》,



    转载本站文章《数组二分查找到二分法的感悟笔记》,
    请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/SortingAlgorithms/9092.html

    收藏
    上一篇：求质数算法的 N 种境界[1] - 试除法和初级筛法
    下一篇：最快排序算法TimSort—各编程语言内置排序(JS/Java/Python/GO等)