以力扣2529为例,题目要求找到正整数的个数和负整数的个数。
一次遍历数组的方法的时间复杂度为O(n),而二分查找的时间复杂度为O(logn)。
使用二分查找思路:所给nums数组升序排列,找到正数的的位置可以转换为找到≥1的位置;找到负数的位置可以理解为<0的位置。
这里给出通用的二分查找:在闭区间[left,right]中找到≥x的位置的java代码。
public int process(int[] nums, int target){
int left = 0;
int right = nums.length-1;
while(left<=right){
int mid = left+(right-left)/2;
if(nums[mid]<target){
left=mid+1;
}else{//之后返回left,要的是找到位置时left不变
right=mid-1;
}
}
return left;
}
>x,<x,≤x的情况:
>x可以转换为≥ (x+1)
<x可以转换为(≥x)-1
≤ x可以转换为(>x)-1