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() 方法來查詢任何元素的下界。