在此示例中，我們將學(xué)習(xí)在Java中實(shí)現(xiàn)二進(jìn)制搜索算法。
在學(xué)習(xí)Java中的二進(jìn)制搜索實(shí)現(xiàn)之前，請(qǐng)確保您了解二進(jìn)制搜索算法的工作原理。
import java.util.Scanner;
//Java中的二進(jìn)制搜索
class Main {
int binarySearch(int array[], int element, int low, int high) {
//重復(fù)這個(gè)過(guò)程，直到指針的高(high)與低(low)相等
while (low <= high) {
//獲取 mid 元素的索引
int mid = low + (high - low) / 2;
//如果要搜索的元素是 mid 元素
if (array[mid] == element)
return mid;
//如果元素小于 mid 元素
//只搜索mid的左側(cè)
if (array[mid] < element)
low = mid + 1;
//如果元素大于mid 元素
//只搜索mid的右側(cè)
else
high = mid - 1;
}
return -1;
}
public static void main(String args[]) {
//創(chuàng)建Main類(lèi)的對(duì)象
Main obj = new Main();
//創(chuàng)建一個(gè)排序的數(shù)組
int[] array = { 3, 4, 5, 6, 7, 8, 9 };
int n = array.length;
//從用戶那里獲取輸入，要搜索的元素
Scanner input = new Scanner(System.in);
System.out.println("輸入要搜索的元素:");
//要搜索的元素
int element = input.nextInt();
input.close();
//調(diào)用二進(jìn)制搜索方法
//傳遞參數(shù): 數(shù)組、元素、第一個(gè)和最后一個(gè)元素的索引
int result = obj.binarySearch(array, element, 0, n - 1);
if (result == -1)
System.out.println("Not found");
else
System.out.println("找到元素，在索引 " + result);
}
}輸出1
輸入要搜索的元素: 6 找到元素，在索引 3
在這里，我們已使用Java掃描器類(lèi)從用戶那里獲取輸入。根據(jù)用戶的輸入，我們使用了二進(jìn)制搜索來(lái)檢查數(shù)組中是否存在該元素。
我們還可以使用遞歸調(diào)用來(lái)執(zhí)行相同的任務(wù)。
int binarySearch(int array[], int element, int low, int high) {
if (high >= low) {
int mid = low + (high - low) / 2;
// 檢查 mid 元素是否為搜索的元素
if (array[mid] == element)
return mid;
//搜索 mid 的左半部分
if (array[mid] > element)
return binarySearch(array, element, low, mid - 1);
//搜索 mid 的右半部分
return binarySearch(array, element, mid + 1, high);
}
return -1;
}在此，該方法binarySearch()將調(diào)用自身，直到找到該元素或if條件失敗為止。