Java 中 C++ lower_bound() 方法的等效实现

---

在本问题中，我们将学习如何在 Java 中实现 C++ lower_bound() 方法的等效算法，以查找已排序数组中给定元素的下界索引。

下界 - 下界是在已排序数组中的索引，该索引包含大于或等于目标元素的最小元素。

我们可以使用搜索算法在不使用内置方法的情况下找到已排序数组中任何元素的下界。在这里，我们将使用线性搜索、迭代和递归二分搜索来获取任何元素的下界。

问题陈述 - 我们给定了一个排序的数值元素数组。我们需要在 Java 中实现 C++ lower_bound() 方法的等效方法，并返回目标元素的下界索引。

使用线性搜索作为 lower_bound() 的替代方法

线性搜索算法遍历数组并将每个数组元素与目标元素进行比较。为了找到特定元素的下界，我们可以将每个元素与目标元素进行比较，如果当前元素大于或等于目标元素，则我们将当前索引视为下界。

算法

• 步骤 1 - 将 'lb' 初始化为 0 以存储下界索引。

• 步骤 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;
      // Iterate over array elements
      while (lb < nums.length) {
         // When the target value is greater than the current array element
         if (target > nums[lb]) {
            lb++;
         }
         // For minimum value greater or equal to the target value
         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;
      
      // Print index of the lower bound
      System.out.println("The lower bound index is for target element is " + get_lower_bound(nums, target));
   }
}

输出

The lower bound index is for target element is 8

• 时间复杂度 - O(N)，因为我们需要遍历数组。

• 空间复杂度 - O(1)，因为我们不使用动态空间。

使用迭代二分搜索作为 lower_bound() 的替代方法

二分搜索是一种高效的搜索算法，它在数组的子部分中搜索。我们将数组从中间分成两部分。如果中间元素大于目标元素，则我们在左侧部分搜索下界。否则，我们在数组的右侧部分搜索下界索引。这样，我们将子数组再次细分为另一个子数组。

算法

• 步骤 1 - 将 'left' 指针初始化为 0，将 'right' 指针初始化为数组的长度。

• 步骤 2 - 使用 while 循环进行迭代，直到 'left' 指针值小于 'right' 指针的值。

• 步骤 3 - 使用 left 和 right 指针值查找中间指针。

• 步骤 4 - 如果中间索引处的元素大于或等于目标元素，则将 'right' 指针更新为中间指针。

• 步骤 5 - 否则，将 'left' 指针更新为 'middle + 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;
      
      // Traverse array
      while (left < right) {
      
         // Get the middle element
         middle = left + (right - left) / 2;
         
         // For finding the element in the left subarray
         if (target <= nums[middle]) {
            right = middle;
         } else {
         
            // For finding the element in the right subarray
            left = middle + 1;
         }
      }
      
      // When the target element is greater than the last element of the array, lower_bound is array length
      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("The lower bound index is for target element is " + get_lower_bound(nums, target));
   }
}

输出

The lower bound index is for target element is 8

• 时间复杂度 - 使用二分搜索算法为 O(logN)。

• 空间复杂度 - O(1)

使用递归二分搜索作为 lower_bound() 的替代方法

在这种方法中，我们将使用递归二分搜索算法在已排序数组中找到目标元素的下界。

算法

• 步骤 1 - 将 'left' 指针初始化为 0，将 'right' 初始化为数组的长度。

• 步骤 2 - 执行 recursive() 函数以查找目标元素的下界。

• 步骤 3 - 在 recursive() 函数中，如果 'left' 指针的值大于 'right' 指针的值，则返回 'left' 值。

• 步骤 4 - 使用 left 和 right 索引值获取中间索引。

• 步骤 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;
      }
      
      // Get the middle element
      int middle = left + (right - left) / 2;
      
      // Make a recursive call for the left subarray
      if (target <= nums[middle]) {
         return recursive(nums, left, middle - 1, target);
      }
      
      // Make a recursive call for the right subarray
      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;
      
      // Print index of the lower bound
      System.out.println("The lower bound index is for target element is " + get_lower_bound(nums, target));
   }
}

输出

The lower bound index is for target element is - 8

• 时间复杂度 - 递归二分搜索为 O(logN)。

• 空间复杂度 - O(1)

就时间复杂度而言，二分搜索算法比线性搜索算法具有更好的效率。但是，我们也可以使用 Array 实用程序类的 binarySearch() 方法来查找任何元素的下界。