Java程序实现二分搜索算法
要理解这个示例,你需要了解以下 Java 编程 主题:
示例:Java 程序实现二分查找算法
import java.util.Scanner;
// Java 中的二分查找
class Main {
int binarySearch(int array[], int element, int low, int high) {
// 重复直到 low 和 high 指针相遇
while (low <= high) {
// 获取中间元素的索引
int mid = low + (high - low) / 2;
// 如果要查找的元素是中间元素
if (array[mid] == element)
return mid;
// 如果元素小于中间元素
// 只在中间元素的左侧查找
if (array[mid] < element)
low = mid + 1;
// 如果元素大于中间元素
// 只在中间元素的右侧查找
else
high = mid - 1;
}
return -1;
}
public static void main(String args[]) {
// 创建 Main 类的对象
Main obj = new Main();
// 创建一个排序数组
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();
// 调用二分查找方法
// 传入参数:数组,元素,第一个和最后一个元素的索引
int result = obj.binarySearch(array, element, 0, n - 1);
if (result == -1)
System.out.println("未找到");
else
System.out.println("元素在索引 " + result + " 处找到");
}
}
输出 1
输入要查找的元素:
6
元素在索引 3 处找到
这里,我们使用了 Java Scanner 类 来获取用户的输入。根据用户的输入,我们使用二分查找来检查数组中是否存在该元素。
我们也可以使用递归调用来执行同样的任务。
int binarySearch(int array[], int element, int low, int high) {
if (high >= low) {
int mid = low + (high - low) / 2;
// 检查中间元素是否是要查找的元素
if (array[mid] == element)
return mid;
// 在中间元素的左侧查找
if (array[mid] > element)
return binarySearch(array, element, low, mid - 1);
// 在中间元素的右侧查找
return binarySearch(array, element, mid + 1, high);
}
return -1;
}
这里,binarySearch()
方法会一直调用自身,直到找到元素或者 if
条件失败。
如果你想了解更多关于二分查找算法的信息,请访问 二分查找算法。