D.二分查找-基础-2529. 正整数和负整数的最大计数

题目链接：2529. 正整数和负整数的最大计数（简单）

算法原理：

解法：二分查找

模板👇

优选算法-二分：18.在排序数组中查找元素的第一个和最后一个位置

利用题目的按 非递减顺序 排列的条件就可以二分处理了，找到负数的最右端点和正数的最左端点

思路一：将二分查找的值设为定值，间接找到不确定的值

击败100.00%

时间复杂度O(Logn)

目标值定为0，因为0恰好是二段性的节点，因此可以有两种角度看待这个目标值0

①左区间最右端的0：[-5,-3-2-1,0,0,0,0,1,4,5,6]

②右区间最左端的0：[-5,-3-2-1,0,0,0,0,1,4,5,6]

第一次遍历找到 最左端的0 进而找到 最后一个负数 ：

二分查找结束后，left和right在0（没有0就在0的右侧），先处理边界情况，看是否全是负数，是0或者正数就正常更新长度即可

第二次遍历找到 最右端的0 进而找到 第一个正数 ：

二分查找结束后，left和right在0（没有0就在0的左侧），先处理边界情况，看是否全是正数，是0或者负数就正常更新长度即可

思路二：直接将二分查找的值设为要找的不确定值

击败100.00%

时间复杂度O(Logn)

比思路一好写一些，但是要理解好每一步，这里的if判断是带等号的，因为0不算正数也不算负数，等于0的时候也要相应移动

答疑

Q1：能不能用一次二分就找到最后的负数和第一个正数呢？

能的，比如先找到最后一个负数的位置，然后left右移找到第一个正数的位置，但是不保证时间复杂度一定是logn，因为当数据[-1,0,0,0,0,0,~,0,0,0,2]，的时候left一直右移就会将时间复杂度弱化到O(N)，所以两次二分还是更稳妥些

Java代码：

class Solution { public int maximumCount(int[] nums) { //利用题目的按 非递减顺序 排列的条件就可以二分处理了 //找到负数的最右端点和正数的最左端点 int n=nums.length; if(n==0) return 0; //利用0来决定二段性：负数 0 正数 //先找最后一个负数(通过最左侧的0来找) int left=0,right=n-1; while(left<right){ int mid=left+(right-left)/2; if(nums[mid]<0) left=mid+1; else right=mid; } //此时在0或者0的右侧（正数） int neg=0; //全是负数 if(nums[left]<0) neg=n; //是0或者正数 else neg=left; //再找第一个正数(通过最右侧的0来找) left=0;right=n-1; while(left<right){ int mid=left+(right-left+1)/2; if(nums[mid]>0) right=mid-1; else left=mid; } //此时在0或者0的左侧 int pos=0; //全是正数 if(nums[left]>0) pos=n; //是0或者负数 else pos=n-(left+1); return Math.max(neg,pos); } }

class Solution { //思路二：直接将二分查找的值设为要找的不确定值 public int maximumCount(int[] nums) { int n=nums.length; if(n==0) return 0; int left=0,right=n-1; //找到负数的最后一个位置 while(left<right){ int mid=left+(right-left+1)/2; if(nums[mid]>=0) right=mid-1; else left=mid; } int neg=nums[left]<0?left+1:0; //找到正数的第一个位置 left=0;right=n-1; while(left<right){ int mid=left+(right-left)/2; if(nums[mid]<=0) left=mid+1; else right=mid; } int pos=nums[left]>0?n-left:0; return Math.max(neg,pos); } }