欢迎光临
我的个人博客网站

算法学习:二分法从入门到精通

今天在力扣看到一道题,顺手写了下,用到了二分法和贪心算法,这里记录一下思路。

二分法查找,也称折半查找,是一种在有序数组中查找特定元素的搜索算法。查找过程可以分为以下步骤:
(1)首先,从有序数组的中间的元素开始搜索,如果该元素正好是目标元素(即要查找的元素),则搜索过程结束,否则进行下一步。
(2)如果目标元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半区域查找,然后重复第一步的操作。
(3)如果某一步数组为空,则表示找不到目标元素。

案例:

题目:从一个排好序的数组中找到固定值的下标。

代码:

function binary_search(arr, key) {     var low = 0,         high = arr.length - 1;      while (low <= high) {         var mid = parseInt((high + low) / 2);         if (key == arr[mid]) {             return mid;         } else if (key > arr[mid]) {             low = mid + 1;         } else if (key < arr[mid]) {             high = mid - 1;         } else {             return -1;         }     } }

从上方的代码中,大致了解了二分法是个什么东西,核心是减少循环次数,用最少的方法,返回准确的结果,节约内存,提高效率。

下面是进阶题目:

传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天,我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

示例 1:

输入:weights = [1,2,3,4,5,6,7,8,9,10], D = 5 输出:15 解释: 船舶最低载重 15 就能够在 5 天内送达所有包裹,如下所示: 第 1 天:1, 2, 3, 4, 5 第 2 天:6, 7 第 3 天:8 第 4 天:9 第 5 天:10  请注意,货物必须按照给定的顺序装运,因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。

示例 2:

输入:weights = [3,2,2,4,1,4], D = 3 输出:6 解释: 船舶最低载重 6 就能够在 3 天内送达所有包裹,如下所示: 第 1 天:3, 2 第 2 天:2, 4 第 3 天:1, 4

示例 3:

输入:weights = [1,2,3,1,1], D = 4 输出:3 解释: 第 1 天:1 第 2 天:2 第 3 天:3 第 4 天:1, 1

下面是我的答案:

var shipWithinDays = function(weights, D) {       let l = Math.max(...weights),r = weights.reduce((n,m) => n + m);     while(l < r){         let r1 = (r - l) % 2 == 1 ? (r - l - 1) / 2: (r - l) / 2;         let mid = l + r1;         if(getWeight(weights,mid) <= D){             r = mid;         }else{             l = mid + 1;         }     }      function getWeight(arr,k){         let sum = 1;         let s = 0;         for(let i = 0; i < arr.length; i++){             if(s + arr[i] <= k){                 s += arr[i];             }else{                 s = arr[i];                 sum++;             }         }         return sum;     }     return l; };

思路是以数组里的最大值为初始值,总和值为结尾值,用二分法来查询,减少次数,有兴趣可以看下代码研究下。

赞(0) 打赏
未经允许不得转载:张拓的天空 » 算法学习:二分法从入门到精通
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

专业的IT技术经验分享 更专业 更方便

联系我们本站主机

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏