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