在此示例中,我们将学习在Java中实现二进制搜索算法。
在学习Java中的二进制搜索实现之前,请确保您了解二进制搜索算法的工作原理。
import java.util.Scanner; //Java中的二进制搜索 class Main { int binarySearch(int array[], int element, int low, int high) { //重复这个过程,直到指针的高(high)与低(low)相等 while (low <= high) { //获取 mid 元素的索引 int mid = low + (high - low) / 2; //如果要搜索的元素是 mid 元素 if (array[mid] == element) return mid; //如果元素小于 mid 元素 //只搜索mid的左侧 if (array[mid] < element) low = mid + 1; //如果元素大于mid 元素 //只搜索mid的右侧 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("Not found"); else System.out.println("找到元素,在索引 " + result); } }
输出1
输入要搜索的元素: 6 找到元素,在索引 3
在这里,我们已使用Java扫描器类从用户那里获取输入。根据用户的输入,我们使用了二进制搜索来检查数组中是否存在该元素。
我们还可以使用递归调用来执行相同的任务。
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()将调用自身,直到找到该元素或if条件失败为止。