算法——二分法
基本介绍
二分法是 每次都排除半个区间,然后在剩余的半个区间内寻找解 的方法,排除半个区间的前提是:区间是有序的,这样一来,当解 小于 区间中点时,就可以在 左子区间 寻找;当解 大于 区间中点时,就可以在 右子区间 寻找。当解 等于 区间中点时,根据要求在子区间寻找或返回。
实现
二分法有两种实现:一种是找 前驱,一种是找 后继。在解决实际问题时需要根据问题的要求不同来采取不同的实现。
后继
定义
在单调递增序列中找
x
x
x 或
x
x
x 的后继 的定义:在单调递增序列 a
中,如果有
x
x
x,则找第一个
x
x
x 的位置;如果没有
x
x
x,则找比
x
x
x 大的 第一个数 的位置。
举例
例如对于 a = [1, 2, 4, 4, 6]
,如果要找
4
4
4 或
4
4
4 的后继,则返回 第一个
4
4
4 的索引 2
;如果要找
3
3
3 或
3
3
3 的后继,则返回比
3
3
3 大的 第一个数(即第一个
4
4
4)的索引 2
。
代码
int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1; // left, right 分别是区间的左端点和右端点
while (left < right) {
int mid = left + (right - left >> 1);
if (target <= nums[mid]) { // 如果目标值小于或等于区间中点
right = mid; // 则在左子区间查找
} else { // 如果目标值大于区间中点
left = mid + 1; // 则在右子区间查找
}
}
return left; // 返回 第一个target的位置 或 第一个比target大的元素的位置
}
前驱
定义
在单调递增序列中找
x
x
x 或
x
x
x 的前驱 的定义:在单调递增序列 a
中,如果有
x
x
x,则找最后一个
x
x
x 的位置;如果没有
x
x
x,则找比
x
x
x 小的 最后一个数 的位置。
举例
例如对于 a = [1, 2, 4, 4, 6]
,如果要找
4
4
4 或
4
4
4 的前驱,则返回 最后一个
4
4
4 的索引 3
;如果要找
5
5
5 或
5
5
5 的前驱,则返回比
5
5
5 小的 最后一个数(即最后一个
4
4
4)的索引 3
。
代码
int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1; // left, right 分别是区间的左端点和右端点
while (left < right) {
int mid = left + (right - left + 1 >> 1);
if (target < nums[mid]) { // 如果目标值小于区间中点
right = mid - 1; // 则在左子区间查找
} else { // 如果目标值大于或等于区间中点
left = mid; // 则在右子区间查找
}
}
return left; // 返回 最后一个target的位置 或 最后一个比target小的元素的位置
}
原文地址:https://blog.csdn.net/qq_61350148/article/details/140334853
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!