高密做网站哪家好,企业网站内容更新,wordpress怎么搬迁,焦作网站制作公司目录 基本介绍实现后继定义举例代码 前驱定义举例代码 基本介绍
二分法是 每次都排除半个区间#xff0c;然后在剩余的半个区间内寻找解 的方法#xff0c;排除半个区间的前提是#xff1a;区间是有序的#xff0c;这样一来#xff0c;当解 小于 区间中点时#xff0c;就… 目录 基本介绍实现后继定义举例代码 前驱定义举例代码 基本介绍
二分法是 每次都排除半个区间然后在剩余的半个区间内寻找解 的方法排除半个区间的前提是区间是有序的这样一来当解 小于 区间中点时就可以在 左子区间 寻找当解 大于 区间中点时就可以在 右子区间 寻找。当解 等于 区间中点时根据要求在子区间寻找或返回。
实现
二分法有两种实现一种是找 前驱一种是找 后继。在解决实际问题时需要根据问题的要求不同来采取不同的实现。
后继
定义
在单调递增序列中找 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小的元素的位置
}
