Toasobi
二分法查找
本文最后更新于2023年09月26日,已超过468天没有更新。如果文章内容或图片资源失效,请留言反馈,我会及时处理,谢谢!
先贴代码:
public int searchInsert(int[] nums, int target) {
int i = 0;
int j = nums.length - 1;
while (i <= j) {
int mid = i + (j - i) / 2;
if (nums[mid] < target) {
i = mid + 1;
} else if (nums[mid] > target) {
j = mid - 1;
} else if (nums[mid] == target) {
return mid;
}
}
return i;
}
一定要注意!int mid = i + (j - i) / 2
不能写成int mid = (i + j) / 2
, 不然会越界。
放一道例题
补充:当数组中有重复数,且需要满足一个条件,返回满足的子串长度等情况,下面这个二分也适用
class Solution {
public int[] successfulPairs(int[] spells, int[] potions, long success) {
Arrays.sort(potions);
int[] res = new int[spells.length];
for (int i = 0; i < spells.length; i++) {
int left = 0, right = potions.length - 1;
int index = potions.length;
while (left <= right) {
int mid = (right - left) / 2 + left;
if ((long)spells[i] * potions[mid] >= success) {
right = mid - 1;
index = mid;
} else {
left = mid + 1;
}
}
res[i] = potions.length - index;
}
return res;
}
}