• home > theory > algorithm > Sorting >

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

    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