在Java中,可以使用遞歸或迭代的方式實現二分搜索算法。以下是一個使用迭代方式實現的示例代碼:
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 如果找不到目標元素,則返回-1
}
在這段代碼中,arr
是一個已經排序的數組,target
是要查找的目標元素。在每一次迭代中,我們計算中間元素的索引mid
,然后根據arr[mid]
與target
的大小關系來更新left
和right
的值,直到找到目標元素或者left > right
為止。如果找到目標元素,則返回它的索引,否則返回-1表示未找到。
另外,也可以使用遞歸的方式實現二分搜索算法,遞歸的實現方式如下:
public static int binarySearchRecursive(int[] arr, int target) {
return binarySearchRecursive(arr, target, 0, arr.length - 1);
}
private static int binarySearchRecursive(int[] arr, int target, int left, int right) {
if (left > right) {
return -1;
}
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
return binarySearchRecursive(arr, target, mid + 1, right);
} else {
return binarySearchRecursive(arr, target, left, mid - 1);
}
}
在這段代碼中,binarySearchRecursive
方法是一個重載方法,它接受一個數組arr
和目標元素target
作為參數,并調用了另一個私有方法binarySearchRecursive
來執行實際的搜索。在私有方法中,我們使用遞歸的方式來執行二分搜索,直到找到目標元素或者left > right
為止。如果找到目標元素,則返回它的索引,否則返回-1表示未找到。