2529. 正整数和负整数的最大计数

题目描述

给你一个按 非递减顺序 排列的数组 nums ，返回正整数数目和负整数数目中的最大值。

• 换句话讲，如果 nums 中正整数的数目是 pos ，而负整数的数目是 neg ，返回 pos 和 neg二者中的最大值。

注意：0 既不是正整数也不是负整数。

思路

因为是一个非递减顺序的数组，因此看上去可以用二分查找去寻找最大的负数和最小的正数。

最开始的想法是分别二分搜索大于 0 和小于 0 的数，那这不就得实现两遍二分了嘛，能不能只实现一次呢？

看了答案，还真行，一次搜索大于等于 0 的数字，下一次搜索大于等于 1 的数字，这不就分别求出负整数的数量和正整数的数量了嘛，而且只需要实现一次二分搜索算法。

那么中间条件是什么呢？参考 搜索模板，我们的目标是寻找左边界，因此会更保守地更新右边界，直到 l<r。

最终代码：

class Solution:
    def maximumCount(self, nums: List[int]) -> int:
        def bin_search(t):
            l, r = 0, len(nums)
            while l < r:
                m = l+((r-l) >> 1)
                if nums[m] >= t:
                    r = m
                else:
                    l = m+1
            return l
        return max(bin_search(0), len(nums)-bin_search(1))

想得太多