更新時間:2024-03-08 來源:黑馬程序員 瀏覽量:
遞歸二分查找是一種經(jīng)典的查找算法,用于在有序數(shù)組中查找特定元素的位置。下面是用Java實現(xiàn)遞歸二分查找的詳細說明:
public class BinarySearch { // 遞歸二分查找方法 public static int binarySearch(int[] arr, int target) { return binarySearch(arr, target, 0, arr.length - 1); } // 輔助遞歸方法 private static int binarySearch(int[] arr, int target, int low, int high) { // 當low大于high時,說明整個數(shù)組已經(jīng)搜索完畢,但未找到目標元素 if (low > high) { return -1; } // 計算中間元素的索引 int mid = low + (high - low) / 2; // 如果中間元素等于目標值,則返回該元素的索引 if (arr[mid] == target) { return mid; } // 如果中間元素大于目標值,則在左半部分繼續(xù)查找 else if (arr[mid] > target) { return binarySearch(arr, target, low, mid - 1); } // 如果中間元素小于目標值,則在右半部分繼續(xù)查找 else { return binarySearch(arr, target, mid + 1, high); } } public static void main(String[] args) { int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int target = 6; int result = binarySearch(arr, target); if (result != -1) { System.out.println("目標元素 " + target + " 的索引為: " + result); } else { System.out.println("目標元素 " + target + " 不存在于數(shù)組中。"); } } }
在這個實現(xiàn)中,我們有兩個方法:
1.binarySearch(int[] arr, int target):
這個方法是公開的二分查找方法,它調(diào)用了輔助遞歸方法,并傳入了數(shù)組、目標值以及數(shù)組的起始和結束索引。
2.binarySearch(int[] arr, int target, int low, int high):
這個方法是私有的輔助遞歸方法。它接受一個數(shù)組、目標值以及搜索范圍的起始和結束索引。在每一次遞歸調(diào)用中,它計算中間元素的索引,然后與目標值進行比較。如果找到目標值,則返回其索引;否則,根據(jù)目標值與中間元素的大小關系,遞歸地在左半部分或右半部分繼續(xù)查找。
在main方法中,我們展示了如何使用這個二分查找算法。我們聲明了一個有序數(shù)組arr,并指定了目標值 target,然后調(diào)用binarySearch方法來搜索目標值在數(shù)組中的位置。最后,根據(jù)返回的結果,輸出相應的信息。