C++ 的 lower_bound() 方法的 Java 等效方法
在这个问题中,我们将学习在 Java 中实现 C++ 的 lower_bound() 方法的等效算法,以查找排序数组中给定元素的下限索引。
下限 - 下限是排序数组中的索引,使得索引包含大于或等于目标元素的最小元素。
我们可以使用搜索算法来查找排序数组中任何元素的下限,而无需使用内置方法。在这里,我们将使用线性搜索、迭代和递归二进制搜索来获取任何元素的下限。
问题陈述 - 我们给出了一个由数字元素组成的排序数组。我们需要在 Java 中实现与 C++ 的 lower_bound() 方法等效的方法,并返回目标元素的下限索引。
使用线性搜索替代 lower_bound()
线性搜索算法遍历数组并将每个数组元素与目标元素进行比较。要找到特定元素的下限,我们可以将每个元素与目标元素进行比较,如果当前元素大于或等于目标元素,则将当前索引视为下限。
算法
步骤 1 - 用 0 初始化"lb"以存储下限索引。
步骤 2 - 开始遍历数组,直到"lb"索引值小于数组的长度。
步骤 3 - 如果目标元素的值大于当前元素,则将"lb"增加 1。
步骤 4 - 如果目标元素的值小于当前元素的值,则返回"lb"值。
步骤5 − 最后返回"lb"值。如果数组的所有元素都小于目标元素,我们可以将数组的长度视为目标元素的下限。
示例
import java.util.Arrays;
public class Main {
static int get_lower_bound(int nums[], int target) {
int lb = 0;
// 迭代数组元素
while (lb < nums.length) {
// 当目标值大于当前数组元素时
if (target > nums[lb]) {
lb++;
}
// 对于大于或等于目标值的最小值
else {
return lb;
}
}
return lb;
}
public static void main(String[] args) {
int nums[] = { 2, 3, 5, 7, 12, 15, 17, 20, 32, 54, 67, 98 };
int target = 22;
// 打印下限的索引
System.out.println("目标元素的下限索引是 " + get_lower_bound(nums, target));
}
}
输出
目标元素的下限索引为 8
时间复杂度 − O(N),因为我们需要遍历数组。
空间复杂度 − O(1),因为我们不使用动态空间。
使用迭代二分搜索替代 lower_bound()
二分搜索是一种高效的搜索算法,它在数组的子部分中进行搜索。我们从中间将数组分成两部分。如果中间元素大于目标元素,我们将在左侧部分搜索下限。否则,我们将在数组的右侧部分搜索下限索引。这样,我们再次将子数组划分为另一个子数组。
算法
步骤 1 - 用 0 初始化"左"指针,用数组的长度初始化"右"指针。
步骤 2 - 使用 while 循环进行迭代,直到"左"指针值小于"右"指针的值。
步骤 3 - 使用左指针和右指针值找到中间指针。
步骤 4 - 如果中间索引处的元素大于或等于目标元素,则用中间指针更新"右"指针。
步骤 5 - 否则,用"中间 + 1' 的值。
步骤 6 - 如果 'left' 指针小于数组的长度,并且 'left' 索引处的元素小于目标元素,则将 'left' 增加 1。
步骤 7 - 返回 'left' 元素的值。
示例
import java.util.Arrays;
public class Main {
static int get_lower_bound(int nums[], int target) {
int left = 0, right = nums.length;
int middle;
// 遍历数组
while (left < right) {
// 获取中间元素
middle = left + (right - left) / 2;
// 用于查找左子数组中的元素
if (target <= nums[middle]) {
right = middle;
} else {
// 用于查找右子数组中的元素
left = middle + 1;
}
}
// 当目标元素大于数组的最后一个元素时,lower_bound 为数组长度
if (left < nums.length && nums[left] < target) {
left++;
}
return left;
}
public static void main(String[] args) {
int nums[] = { 2, 3, 5, 7, 12, 15, 17, 20, 32, 54, 67, 98 };
int target = 22;
System.out.println("目标元素的下限索引为 " + get_lower_bound(nums, target));
}
}
输出
目标元素的下限索引为 8
时间复杂度 - 使用二分搜索算法的 O(logN)。
空间复杂度 - O(1)
使用递归二分搜索替代 lower_bound()
在此方法中,我们将使用递归二分搜索算法在排序数组中找到目标元素的下限。
算法
步骤 1 - 用 0 初始化"left"指针,用数组的长度初始化"right"。
步骤 2 - 执行 recursive() 函数以查找下限目标元素的。
步骤 3 - 在 recursive() 函数中,如果"左"指针的值大于"右"指针的值,则返回"左"值。
步骤 4 - 使用左和右索引值获取中间索引。
步骤 5 - 如果目标元素小于或等于中间索引处的元素,则对数组的左侧部分进行递归调用。
步骤 6 - 否则,使用 recursive() 函数调用对数组的右侧部分进行递归调用。
示例
import java.util.Arrays;
public class Main {
static int recursive(int nums[], int left, int right, int target) {
if (left > right) {
return left;
}
// 获取中间元素
int middle = left + (right - left) / 2;
// 对左子数组进行递归调用
if (target <= nums[middle]) {
return recursive(nums, left, middle - 1, target);
}
// 对右子数组进行递归调用
return recursive(nums, middle + 1, right, target);
}
static int get_lower_bound(int nums[], int target) {
int left = 0, right = nums.length;
return recursive(nums, left, right, target);
}
public static void main(String[] args) {
int nums[] = { 2, 3, 5, 7, 12, 15, 17, 20, 32, 54, 67, 98 };
int target = 22;
// 打印下限索引
System.out.println("目标元素的下限索引为 " + get_lower_bound(nums, target));
}
}
输出
目标元素的下限索引为 - 8
时间复杂度 - O(logN)(递归二分查找)。
空间复杂度 - O(1)
二分查找算法在时间复杂度方面比线性查找算法效率更高。但是,我们也可以使用 Array 实用程序类的 binarySearch() 方法来查找任何元素的下限。
相关文章
有用资源
java 参考教程 - 该教程包含有关 java 的更多信息:https://www.cainiaomax.com/java/

