- C++
关于二分:二分算法速通!
- @ 2026-2-10 19:54:14
本篇主要讲述二分是什么并如何使用二分,内容简便,非常适合萌新学习,如有遗漏或不足,欢迎补充!
二分算法的主要应用:二分查找和是二分答案(根本上来说二分查找就是二分答案的究极简化版)
二分查找就是先建立左右指针,计算中间位置,比较中间元素与目标值,并根据比较结果调整指针范围(如果中间元素>目标值,那么右指针向左移,反之中间元素<目标值,则左指针向右移,无论是哪种情况,都要将其中一个指针位移到中间元素上),直到找到目标值或左右指针重合即为答案(细品这段话,这就是二分的核心逻辑!)。
理解了二分查找,二分答案就是二分查找的基础上引入 check(检查)函数,即检查中间元素是否符合题意,再根据题意考虑将哪一个指针移到中间元素上,这一点根据题意来就行了,我只能说:熟能生巧!
tips:(需要一定数学基础和思维理解): 想判断一道题能否使用二分算法,只需要判断它的二分性就行了(不理解“二分性”是什么?我举个例子,一个大箱子需要100个人搬,那么小于100个人肯定搬不了,而只要人数>=100就可以搬了。我们记一个数组,把搬不了的人数记作0,搬的了的人数记作1。 一开始没有人搬,然后搬箱子的人数不断增加,那么数组为0000000……1111111,也就是说,人数是在不断进行有意义的增加,它会在增加到一定程度时(人数=100)发生 单调的改变(单调的意思便是 只增加或只减少 )。 如果你理解了以上内容,那么恭喜你:你已经入门了二分这项重要的基础算法!
例题:二分查找,伐木工(二分答案),英语课 (前两个全平台都有,“英语课”为本平台原创),可以对照本论题入门二分。
以上便是二分内容速通,希望对你的二分有所帮助!
1 条评论
-
20250001 🤡 LV 10 @ 2026-2-10 21:30:18
可以举一些例题上来
👍 4🤡 4🤣 4🤔 2❤️ 2🍋 2😕 2😄 2🌿 2👎 1
- 1