Java 交互式和递归式二叉搜索
Harshit Jindal
2023年1月30日
2021年2月28日
注意
如果你想详细了解二叉搜索，那么可以参考二叉搜索算法一文。
二叉搜索算法的迭代实现
假设我们有一个未排序的数组 A[]，包含 n 个元素，我们想找到一个元素 X。
-
设
lo为0，hi为n - 1。 -
当
lo<hi。- 设置
mid=lo + (hi - lo)/2。 - 如果
A[mid] == X，我们找到了元素，返回索引mid。 - 如果
A[mid] < X，则丢弃左半部分元素，并将lo设为mid+1。 - 否则，如果
A[mid] > X，则丢弃右半部分元素，并将hi设为mid-1。
- 设置
-
未找到元素，所以返回
-1。
Java 二叉搜索的迭代程序
class BinarySearch {
int binarySearch(int arr[], int x)
{
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] < x)
lo = mid + 1;
else
hi = mid - 1;
}
return -1;
}
public static void main(String args[])
{
BinarySearch ob = new BinarySearch();
int arr[] = { 1, 2, 3, 4, 5 };
int n = arr.length;
int x = 5;
int position = ob.binarySearch(arr, x);
if (position == -1)
System.out.println("Element not present");
else
System.out.println("Element found at index: " + position);
}
}
输出：
Element found at index: 4
递归二叉搜索算法
假设我们有一个无序数组 A[]，包含 n 个元素，我们想找到一个元素 X。
-
初始化
lo为0，hi为n-1。 -
如果
lo>hi，说明我们已经用尽了数组的搜索空间，返回-1。 -
计算中点
mid为lo+(hi-lo)/2。它将数组分为两部分：下半部分是0到mid - 1的元素，上半部分是mid到n - 1的元素。 -
如果
X=mid，我们发现目标元素返回mid。 -
如果
X小于mid，通过递归调用binarysearch(arr, lo, mid-1)搜索数组的下半部分。 -
Else 如果
X大于mid，则通过递归调用binarysearch(arr, mid+1, hi)来搜索数组的上半部分。
Java 二叉搜索的递归程序
class BinarySearch {
int binarySearch(int arr[], int lo, int hi, int x) {
if (hi >= lo && lo < arr.length - 1) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, lo, mid - 1, x);
return binarySearch(arr, mid + 1, hi, x);
}
return -1;
}
public static void main(String args[]) {
BinarySearch ob = new BinarySearch();
int arr[] = { 1, 2, 3, 4, 5 };
int n = arr.length;
int x = 2;
int position = ob.binarySearch(arr, 0, n - 1, x);
if (position == -1)
System.out.println("Element not found !!!");
else
System.out.println("Element found at index: " + position);
}
}
输出：
Element found at index: 1
Arrays.binarySearch() 概述
Java 为我们提供了一个现成的函数 Arrays.binarySearch()，这样我们就不用自己去实现这个函数了。它是一个非常简单易用且有效实现的方法，而且不容易出错。
语法
public static int binarySearch(T arr, T key )
T 可以是下列任何一种。int, float, short, long, byte, char, double, 甚至还有用户定义的 Object。
就像我们实现的二叉搜索一样，它也要求对数组进行排序，否则结果是无法定义的。它使用二叉搜索算法对数组进行搜索，找到目标元素的索引。如果目标元素有多个出现，那么它可以返回其中任何一个元素的索引。
参数
Arr |
输入数组 |
Key |
我们要搜索的目标元素。 |
返回值
如果它找到了目标元素，那么就返回它的索引，否则就返回 beg - 1，其中 beg 是数组搜索空间的起始索引。否则，它返回 beg - 1，其中 beg 是数组搜索空间的起始索引。
Java 二叉搜索程序
import java.util.Arrays;
class BinarySearchExample{
public static void main(String args[]){
int arr[] = {1,2,3,4,5};
int key = 2;
int result = Arrays.binarySearch(arr,key);
if (result < 0)
System.out.println("Element is not found!");
else
System.out.println("Element is found at index: "+result);
}
}
输出：
Element is found at index: 1
Author: Harshit Jindal
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn