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

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

下界(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 - 使用左右指针的值找到中间指针。

• 步骤4 - 如果中间索引处的元素大于或等于目标元素，请使用中间指针更新’right’指针。

• 步骤5 - 否则，请使用’中间+1’的值更新’left’指针。

• 步骤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 − 执行递归()函数，找到目标元素的下界。

• 步骤3 − 在递归()函数中，如果’left’指针的值大于’right’指针的值，则返回’left’的值。

• 步骤4 − 使用左右索引值获取中间索引。

• 步骤5 − 如果目标元素小于等于中间索引处的元素，则对数组的左半部分进行递归调用。

• 步骤6 − 否则，使用递归()函数调用对数组的右半部分进行递归调用。

示例

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()方法来找到任何元素的下边界。