二、二分算法
灵神提单：二分算法（二分答案/最小化最大值/最大化最小值/第K小）
一、二分查找
1.1、基础
34. 在排序数组中查找元素的第一个和最后一个位置（20250401更新）
题目：
给你一个按照非递减顺序排列的整数数组
nums，和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值
target，返回[-1, -1]。你必须设计并实现时间复杂度为
O(log n)的算法解决此问题。
>=, <= 都可以转化用 binarySearch 来转化
比如>=x 直接用， <=x 可以转化成>= x+1, 最后取下标减一。
两端闭区间[left, right]
class Solution {
public int[] searchRange(int[] nums, int target) {
int start = binarySearch(nums, target);
if (start == nums.length || nums[start] != target) {
return new int[] { -1, -1 };
}
int end = binarySearch(nums, target + 1) - 1;
return new int[] { start, end };
}
int binarySearch(int[] nums, int target) {
// 两端闭区间的情况[left, right]
// 两端闭区间的时候，left移动到mid+1， right移动到mid-1
int left = 0;
int right = nums.length - 1;
// 区别地方：两端闭，当left=right的时候也需要处理
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
}左闭右开区间[left, right)
class Solution {
public int[] searchRange(int[] nums, int target) {
int start = binarySearch(nums, target);
if (start == nums.length || nums[start] != target) {
return new int[] { -1, -1 };
}
int end = binarySearch(nums, target + 1) - 1;
return new int[] { start, end };
}
int binarySearch(int[] nums, int target) {
// 左闭右开区间[left, right)
// 左闭右开的时候，右节点在移动时就移动到mid的位置
int left = 0, right = nums.length;
// 区别地方，左闭右开因为取不到右侧，所以最后一个点就是left+1=right，在移动就跳出循环了
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}两端开区间(left, right )
class Solution {
public int[] searchRange(int[] nums, int target) {
int start = binarySearch(nums, target);
if (start == nums.length || nums[start] != target) {
return new int[] { -1, -1 };
}
int end = binarySearch(nums, target + 1) - 1;
return new int[] { start, end };
}
int binarySearch(int[] nums, int target) {
// 两端开区间(left, right)
// 两端开区间，那么left移动到mid， right移动到mid
int left = -1, right = nums.length;
// 区别地方，两端开区间相对于左闭右开，左指针左移了一位。
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid;
} else {
right = mid;
}
}
return right;
}
}704. 二分查找（20250401更新）
二分查找最基础的题，直接套用框架求解，都不需要做额外的操作。
2529. 正整数和负整数的最大计数（20250401更新）
给你一个按 非递减顺序 排列的数组
nums，返回正整数数目和负整数数目中的最大值。
- 换句话讲，如果
nums中正整数的数目是pos，而负整数的数目是neg，返回pos和neg二者中的最大值。注意：
0既不是正整数也不是负整数。
由于数组是有序的，我们可以二分找到第一个>=0的数的下标i，那么下标在[0, i-1]中的数都是小于0的，这恰好有i个。
同样的，二分找到第一个>0的数的下标j，那么下标[j, n-1]中的数都大于0，这里有n-j个。
所以通过二分查找第一个>=0的和第一个>0的位置，就可以用O(logn)的时间解决。
Java
class Solution {
public int maximumCount(int[] nums) {
// >=0, >1的位置
int start = ds(nums, 0);
int end = ds(nums, 1);
return Math.max(start, nums.length - end);
}
int ds(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
}