正在加载喵
（因文稿部分丢失，后续需要进行补充更新）
如果数据存放在链表中，访问一个元素我们都得通过遍历，有遍历的功夫我们早就找到了这个元素，因此，在链表中不适合使用二分查找。
其中「有序」这个条件可以放宽，半有序数组或者是山脉数组里都可以应用二分查找算法。
旋转和山脉数组的值都有规律可循，元素的值不是随机出现的，在这个特点下，「减治思想」就可以应用在旋转数组和山脉数组里的一些问题上。我们可以把这两类数组统一归纳为部分有序数组
这种二分法用于查找一个有范围的数，也被称为「二分答案」，或者「二分结果」，也就是在「答案区间」里或者是「结果区间」里逐渐缩小目标元素的范围；
思路 1：在循环体中查找元素 思路 2：在循环体中排除目标元素一定不存在的区间
大 O 不在乎常数差距，只在乎增长趋势。
故 O(2⋅logn)=O(logn)
推导
| 方法 | 思路 | 时间复杂度 | 是否符合题目要求 |
|---|---|---|---|
| 线性扩展法 | 找到一个目标后向左右扩展 | O(n) | 不符合 |
| 二分两次法 | 分别用二分找左边界和右边界 | O(log n) | 符合 |
情况一：nums[mid] > nums[right]
说明 最小值一定在右边（mid 不可能是最小值）。
因为 nums[mid] 比 nums[right] 大，说明从 mid+1 到 right 这段区间里一定有更小的值。
所以我们可以放心地写：
情况二：nums[mid] < nums[right]
说明 最小值在左边，而且 mid 本身可能就是最小值。
所以不能丢掉 mid，只能写：
保留 mid 继续判断。
当 left == right 时，就是最小值的下标。
-> 绕路 mid左右加和 不影响复杂度 但只需要判断 哪一边有序，或者 最小值在哪一边，就能决定收缩方向
每次二分时，至少有一半区间是有序的。
if nums[left] <= nums[mid] → 左边有序判断 target 是否在有序区间里。
小云同学还期望改造刚才的无重复数组 但她考虑到时间复杂度在最坏情况下退化为 O(n) 故给搜索最小数的时候也加上了 right--;但很不幸无法 AC（280/282）
样例是
nums = [1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1] target = 2
她发现在有大量重复元素的情况下（如样例），searchMin 找到的 旋转点位置不唯一，从而导致分段二分出错 她终于发现是算法思路限制 无法通过修补通过这个样例
使用相对熟悉的多步二分直接 AC 但请 GPT 大人纠正了一些错误代码习惯 摘录在这里
mountainArr.get(mid)在 find 和 getmax 中，每次判断都调用了两次 mountainArr.get(mid) 或 mountainArr.get(mid+1)。
left <= right 而不是 left < right原来的 while(left < right) 循环会在循环结束后再单独判断 mountainArr.get(left)，加上上面的优化可以直接写成标准二分查找形式 left <= right，逻辑更干净。
但通过刚才经验了解不是很熟练一次二分 故写了一下 有些小问题记录一下
int m2 = mountainArr.get(mid+1); 可能越界
mid == mountainArr.length() - 1 时，mid+1 会越界。m2 前先判断 mid < length - 1，否则不要去访问 mid+1。但仍不能 AC 对于 样例点 输入 [0,5,1] 0 输出 -1 有问题
这才意识到这种做法无法保证返回最小下标 故放弃
给定两个正序数组 nums1 和 nums2，求它们合并后的中位数，时间复杂度 O(log(m+n)) 暗示我们不能真的合并数组，而要用「二分法」。
中位数把一个有序数组分成两部分：
如果我们能把两个数组合并后的「左边」和「右边」拆开，就能直接得到中位数。
我们希望 leftA + leftB 和 rightA + rightB：
记：
这个公式保证左右两边长度关系正确（总长度奇偶都通用）
然后要满足：
为了避免处理太多边界情况，我们规定 A 是短数组（m ≤ n）。
[0, m] 范围里二分查找 iA[i-1] > B[j] → i 太大，向左移动B[j-1] > A[i] → i 太小，向右移动注意边界处理：
另在 Java 中：
Integer.MAX_VALUEInteger.MIN_VALUE在C++中
正无穷 → INT_MAX（<climits> 中定义）
负无穷 → INT_MIN
划分完成后：
数学难度较大 写了一个还没 AC 的代码 比较头晕 后清清脑子再补 先贴一个题解
答案空间可枚举 + 存在单调性函数 + 能通过函数值判断往左还是往右。
x 是否「可行」或「过大/过小」。
count = # {nums[i] ≤ mid}。count > mid → 说明重复数一定在左半边。count 只会变大或相等。f(x) = sum(min(a, x))。f(x) 最接近 target，可能会停在两个候选解之间 → 需要比较。-> 在 值的范围 上做二分，而不是在数组下标上
在没有重复的情况下：
在区间 [1, mid] 里，最多应该有 mid 个不同的数。
所以 count ≤ mid。
如果 count > mid：
说明在 [1, mid] 这个区间里，元素的数量超过了它本应能容纳的数量，这区间里一定有重复数。
→ 因此我们缩小搜索区间到 [left, mid]。
如果 count ≤ mid：
说明 [1, mid] 内没有超过容量，重复数只能出现在 [mid+1, right]。
while(left <= right){
int mid = left + (right - left)/2;
if (nums[mid] == target){
return mid;
}
else if (nums[mid] > target){
right = mid - 1;
}
else{
left = mid + 1;
}
}
public static int search(int[] nums, int target) {
return binarySearch(nums, target, 0, nums.length - 1);
}
private static int binarySearch(int[] nums, int target, int left, int right) {
if (left > right) {
return -1;
}
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
return binarySearch(nums, target, left, mid - 1);
} else {
return binarySearch(nums, target, mid + 1, right);
}
}
public int[] searchRange(int[] nums, int target) {
int left = find(nums, target, true); // 左
int right = find(nums, target, false); // 右
return new int[]{left, right};
}
private int find(int[] nums,int target,boolean isLeft){
int right = nums.length - 1,left = 0;
int bound = -1;
while(left <= right){
int mid = left + (right - left)/2;
if(nums[mid] == target){
bound = mid;
if(isLeft){
right = mid - 1;
}
else{
left = mid + 1;
}
}
else if(nums[mid] > target){
right = mid - 1;
}
else{
left = mid + 1;
}
}
return bound;
}
left = mid + 1;
right = mid;
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while(left < right){
int mid = left + (right - left)/2;
if(nums[mid] > nums[right]){
left = mid + 1;
} else{
right = mid;
}
}
return nums[right];
}
while(left < right){
int mid = left + (right - left)/2;
if(nums[mid] > nums[right]){
left = mid + 1;
} else if(nums[mid] < nums[right]){
right = mid;
} else{
right--;
}
}
return nums[right];
public int search(int[] nums, int target) {
int mainIndex = searchMin(nums);
int leftIndex = getBound(nums,target,0,mainIndex - 1);//左面
int rightIndex = getBound(nums,target,mainIndex,nums.length - 1);//右面
if (leftIndex != rightIndex) return Math.max(leftIndex,rightIndex);
else return -1;
}
private int getBound(int[] nums,int target,int left,int right){
while(left <= right){
int mid = left + (right - left)/2;
if(nums[mid] == target){
return mid;
}
else if(nums[mid] > target){
right = mid - 1;
}
else{
left = mid + 1;
}
}
return -1;
}
private int searchMin(int[] nums){
int left = 0;
int right = nums.length - 1;
while(left < right){
int mid = left + (right - left)/2;
if (nums[mid] < nums[right]){
right = mid;
}
else if (nums[mid] > nums[right]){
left = mid + 1;
}
}
return right;
}
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
// 左边有序
if (nums[left] <= nums[mid]) {
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// 右边有序
else {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
while(left <= right){ //错点 1
int mid = left + (right - left)/2;
if(nums[mid] == target) return true;
// 遇到重复元素无法判断哪边有序
if(nums[left] == nums[mid] && nums[mid] == nums[right]){
left++;
right--;
}
// 左半边有序
else if(nums[mid] >= nums[left]){
if(target >= nums[left] && target < nums[mid]){
right = mid - 1;
} else {
left = mid + 1;
}
}
// 右半边有序
else {
if(target > nums[mid] && target <= nums[right]){
left = mid + 1;
} else {
right = mid - 1;
}
}
}
while(left < right){
int mid = left + (right - left)/2;
if(arr[mid] < arr[mid+1]){
left = mid + 1;
}
else{
right = mid;
}
}
private int getPeak(MountainArray mountainArr){
int left = 0, right = mountainArr.length() - 1;
while(left < right){
int mid = left + (right - left)/2;
int midVal = mountainArr.get(mid);
int midNextVal = mountainArr.get(mid + 1);
if(midVal < midNextVal) left = mid + 1;
else right = mid;
}
return left;
}
private int binarySearch(MountainArray mountainArr, int target, int left, int right, boolean increasing){
while(left <= right){
int mid = left + (right - left)/2;
int midVal = mountainArr.get(mid);
if(midVal == target) return mid;
if(increasing){
if(midVal < target) left = mid + 1;
else right = mid - 1;
} else {
if(midVal > target) left = mid + 1;
else right = mid - 1;
}
}
return -1;
}
public int findInMountainArray(int target, MountainArray mountainArr) {
int left = 0;
int right = mountainArr.length() - 1;
while(left <= right){
int mid = left + (right - left)/2;
int m1 = mountainArr.get(mid);
if(m1 == target) return mid;
if(mid < mountainArr.length() - 1){ //越界检查
int m2 = mountainArr.get(mid + 1);
if(m1 < m2) { //上升区间,m1上升
if(m1 < target) left = mid + 1; //m1小于目标值 去掉左边
else right = mid - 1;
}
else{ //下降区间
if(m1 < target) right = mid - 1;
else left = mid + 1;
}
}
else right = mid - 1; // mid 已经在数组最后，直接往左缩
}
return -1;
}
i + j = (m + n + 1) / 2
A[i-1] ≤ B[j] // A左最大 ≤ B右最小
B[j-1] ≤ A[i] // B左最大 ≤ A右最小
max_of_left = max(A[i-1], B[j-1])
min_of_right = min(A[i], B[j])
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) { //保证nums1是短数组
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.length;
int n = nums2.length;
int left = 0,right = m;//表示可选择的空位
while(left <= right){
//i,j 表示切点
int i = left + (right - left)/2;
int j = (m + n + 1)/2 - i;
int A_left = (i == 0) ? Integer.MIN_VALUE : nums1[i-1];// 左面没有元素
int A_right = (i == m) ? Integer.MAX_VALUE : nums1[i]; // 右面没有元素
int B_left = (j == 0) ? Integer.MIN_VALUE : nums2[j-1];
int B_right = (j == n) ? Integer.MAX_VALUE : nums2[j];
if( A_left <= B_right && B_left <= A_right){ //划分正确
if ((m + n) % 2 == 0) {
return (Math.max(A_left, B_left) + Math.min(A_right, B_right)) / 2.0;
} else {
return Math.max(A_left, B_left);
}
}
if(A_left > B_right){ //A左最大 > B右最小 i太大 向左移
right = i - 1; //通过i来影响right
}
if(B_left > A_right){// B左最大 > A右最小 i小 向右移
left = i + 1;
}
}
return -1;
}
public int mySqrt(int x) {
if (x == 0) {
return 0;
}
int left = 1;
int right = x / 2;
while (left < right){
int mid = (left + right + 1) / 2; //向上取整
if (mid > x / mid) {
// 大于等于mid的数一定不是解，下一轮搜索的区间为 [left, mid - 1]
right = mid - 1;
} else {
left = mid;
}
}
return left;
}
public int findDuplicate(int[] nums) {
int left = 1, right = nums.length - 1; // 搜索的值域范围 [1, n]
while (left < right) {
int mid = left + (right - left) / 2;
int count = 0;
// 统计 <= mid 的元素个数
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= mid) count++;
}
if (count > mid) {
// 重复数在 [left, mid]
right = mid;
} else {
// 重复数在 [mid+1, right]
left = mid + 1;
}
}
return left;
}
public int findDuplicate(int[] nums) {
int left = 1, right = nums.length - 1; // 搜索的值域范围 [1, n]
while (left < right) {
int mid = left + (right - left) / 2;
int count = 0;
// 统计 <= mid 的元素个数
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= mid) count++;
}
if (count > mid) {
// 重复数在 [left, mid]
right = mid;
} else {
// 重复数在 [mid+1, right]
left = mid + 1;
}
}
return left;
}
public int findBestValue(int[] arr, int target) {
int len = arr.length;
int left = 0,right = findMax(arr,len);
while(left < right){
int mid = left + (right - left)/2;
int count = js(arr,len,mid);
System.out.println(mid);
System.out.println(count);
if(target <= count) right = mid;
//错点一 原为right = mid - 1在「最接近目标」的题里，我们不是要严格排除 mid，而是要保留它作为候选值。
else left = mid + 1;
}
int c1 = Math.abs(js(arr,len,left) - target);
int c2 = (left > 0) ? Math.abs(js(arr, len, left - 1) - target) : Integer.MAX_VALUE;
//错点二 int c2 = Math.abs(js(arr,len,left - 1) - target); left-1可能越界
if(c1 == c2) return Math.min(left,left - 1);
else if(c1 > c2) return left - 1;
else return left;
}
private int js(int[] nums,int len,int mid){
int count = 0;
for(int i = 0;i < len;i++){
count += Math.min(nums[i],mid);
}
return count;
}
private int findMax(int[] nums,int len){
int max = 0;
for(int i = 0;i < len;i++){
max = Math.max(max, nums[i]);
}
return max;
}