边界查找

副标题 / 摘要 给定一个有序整数数组，如何在 O(log n) 时间内分别统计负数和正数的个数，并返回两者中的较大值？这道「Maximum Count of Positive & Negative Integers」正是边界型二分的练习题。本文用上下界二分一次性搞定负数结束和正数起点。 预计阅读时长：8~10 分钟 适用场景标签：二分查找、边界计数、排序数组 SEO 关键词：maximum count, positive negative, 二分统计, 上下界, 有序数组计数 目标读者与背景 目标读者 已经会写 basic binary search，希望进阶到“计数型二分”的同学； 在工程中有基于排序数据做区间计数需求的工程师； 准备面试，想把二分查找的上下界技巧练熟的开发者。 背景 / 动机 在各种日志 / 指标 / 数据分析场景中，我们经常会对有序数据做计数： 比如统计小于 0 的条目数量； 统计大于某个阈值的条目数量； 找到“负数段结束”和“正数段开始”的位置。 这道 LeetCode 题「Maximum Count of Positive & Negative Integers」是这类需求的简化模型，非常适合作为上下界二分的练习。 A — Algorithm（题目与算法） 题目重述 给定一个按非降序排序的整数数组 nums。 数组中可能包含负数、0 和正数。 定义： countNeg = 数组中小于 0 的元素数量； countPos = 数组中大于 0 的元素数量。 请返回 max(countNeg, countPos)。 输入 ...

题目要求 先看官方示例中的输入 nums = [5,7,7,8,8,10] 和 target = 8。答案必须是完整范围 [3,4]；只返回下标 3 或 4，都没有回答目标值第一次和最后一次出现在哪里。 给定一个按非递减顺序排列的整数数组 nums 和一个整数 target： 如果 target 存在，返回它第一次和最后一次出现的下标 [first, last]。 如果 target 不存在，返回 [-1, -1]。 题目最终要求算法的运行时间为 O(log n)。 LeetCode 使用以下方法契约： class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: 官方示例 输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4] 输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1] 输入：nums = [], target = 0 输出：[-1,-1] 约束 0 <= nums.length <= 10^5 -10^9 <= nums[i] <= 10^9 -10^9 <= target <= 10^9 nums 按非递减顺序排列。 Step 1：先得到一个肯定正确的范围 当目标值连续出现多次时，怎样保证同时记录最早和最晚的下标？ ...