C++ 的 lower_bound() 方法的 Java 等效方法

javaobject oriented programmingprogramming更新于 2024/10/8 3:24:17

在这个问题中,我们将学习在 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() 方法来查找任何元素的下限。


相关文章


有用资源