SuperAPI AI 工具集

binary-search

编程与开发

查看项目

更新于 10-15 23:46

技能介绍

用途:该技能面向二分查找类问题,核心思想是二分查找不只适用于有序数组,也适用于任何单调谓词,典型模式是“找到使条件成立的最小 X”,即在答案空间上二分。

主要能力与规则:对有序数组的插入点,使用 bisect.bisect_left/bisect.bisect_right;对“最小化最大值”或“最大化最小值”问题,在答案上二分并检查可行性;计算中点时始终使用 lo + (hi - lo) // 2 以避免溢出;搜索旋转数组时先判断哪一半是有序的;禁止在没有单调谓词的无序数据上二分。

复杂度:时间复杂度为 O(log n),当题目出现“有序”或“单调”时即可考虑二分。

示例:对于“最小化最大负载”问题,在答案空间上二分,检查 feasible(mid) 能否划分为 k 组且每组不超过 mid,并用 lo + (hi - lo) // 2 避免溢出。

限制:资料未提供具体安装命令、代码实现、平台支持或收费信息。