Java 中的二分查找()-java教程-PHP中文網

在 Java 中，binarySearch() 是一種幫助使用二分搜尋演算法從多個元素中搜尋特定鍵元素的方法。為了執行此操作，元素必須按升序排序。如果沒有排序，可以使用Arrays.sort(arr)方法進行排序。否則，結果被認為是未定義的。與線性搜尋相比，二分搜尋被認為更快。因此，二分查找的時間複雜度為 O(log n)。此外，binarySearch() 方法可以從 java.util.Arrays 套件中實例化。有關 binarySearch() 方法的更多詳細資訊將在以下部分中討論。

文法：

開始您的免費軟體開發課程

網頁開發、程式語言、軟體測試及其他

public static int binarySearch(Object[] a, Object key)

登入後複製

這裡參數a和key分別是要找的陣列和要找的值。

binarySearch() 方法傳回正在搜尋的關鍵元素的索引。在未找到關鍵元素的情況下，將傳回原本要插入的關鍵元素的插入點。如果搜尋的關鍵元素與陣列中的其他元素不可比較，則會拋出稱為 ClassCastException 的例外。

BinarySearch() 方法在 Java 中如何運作？

讓我們看看這個方法在 Java 中是如何運作的：

假設k是要搜尋的關鍵元素。將 k 與陣列的中間元素進行比較。
如果 k 與中間位置的元素匹配，則必須傳回中間索引。
否則，如果k比中間位置的元素高，那麼k只能在中間元素的右邊找到。
否則可以在中間元素的左邊找到。

在 Java 中實作 BinarySearch() 的範例

以下是一些使用 BinarySearch() 方法的程式範例。

範例#1

代碼：

import java.util.Arrays;
public class BinarySearchExample
{
public static void main(String[] args)
{
//create a byte array
byte ba[] = {05, 10, 15, 20, 25, 30};
//create a character array
char ca[] = {'a', 'n', 's', 'p', 'v', 'i', 'd'};
//create an integer array
int ia[] = { 10, 20, 15, 22, 35};
//create a double array
double da[] = {10.1 , 15.34 , 22.25, 13.5};
//create a float array
float fa[] = {13.2f, 25.1f , 22.2f , 43.5f };
//sort all the arrays that created above
Arrays.sort(ba);
Arrays.sort(ca);
Arrays.sort(ia);
Arrays.sort(da);
Arrays.sort(fa);
//enter the key elements that has to be searched in the array
byte bKey = 15;
char cKey = 'i';
int iKey = 22;
double dKey = 15.34;
float fKey = 22.2f;
System.out.println("Element "+ bKey + " is found at the position of " + Arrays.binarySearch(ba,bKey) );
System.out.println("Element "+ cKey + " is found at the position of " + Arrays.binarySearch(ca,cKey) );
System.out.println("Element "+ iKey + " is found at the position of " + Arrays.binarySearch(ia,iKey) );
System.out.println("Element "+ dKey + " is found at the position of " + Arrays.binarySearch(da,dKey) );
System.out.println("Element "+ fKey + " is found at the position of " + Arrays.binarySearch(fa,fKey) );
}
}

登入後複製

輸出：

Java 中的二分查找()

上述程式中使用 Arrays 對陣列進行排序後，建立了字元、整數、浮點、雙精確度和位元組等不同類型的陣列。 Sort() 方法中宣告了需要在陣列中搜尋的元素。然後使用 Arrays.binarySearch() 方法列印搜尋到的元素的索引。

假設給定一個陣列中不存在的關鍵元素；輸出是什麼？

為了找到這一點，讓我們更改關鍵元素的程式碼，如下所示。

位元組 bKey = 15;
char cKey = ‘i’;
int iKey = 89;
雙 dKey = 15.34;
浮動 fKey = 22.2f;

也就是說，iKey=89 不存在於陣列中，那麼輸出將顯示如下。

Java 中的二分查找()

我們可以看到，位置列印為-6。這是因為，如果搜尋某個元素但未找到，則如果該元素存在，則將傳回索引的負值。即，int ia[] = { 10, 20, 15, 22, 35} 是給定的陣列。如果存在 89，則數組將為 int ia[] = { 10, 20, 15, 22, 35, 89};

可以清楚地看到索引將為 6。由於原始數組中不存在該索引，因此在上面的輸出中傳回了該特定索引的負值。

範例#2

二分查找也可以藉助遞歸來完成，如下圖所示。

代碼：

//sample class
class BinarySearchExample{
public static int binarySearch(int a[], int f, int l, int k){
//if last element is greater than or equal to first element
if (l>=f)
{
//find the mid
int m = f + (l - f)/2;
//if the key element that is searching is found in middle position, return mid position
if (a[m] == k)
{
return m;
}
//if key element is less than element in middle position, search the left <u>subarray</u>
if (a[m] > k){
return binarySearch(a, f, m-1, k);
}
//if key element is greater than the element in middle position, search the right <u>subarray</u>
else{
return binarySearch(a, m+1, l, k);
}
}
return -1;
}
public static void main(String args[]){
//initialise the array
int a[] = {34,45,54,68,79};
int k = 68;
int l = a.length-1;
//store the position in variable res
int res = binarySearch(a,0,l,k);
if (res == -1)
System.out.println("Sorry!! Can't find the element....!");
else
System.out.println("Element is found at the position: "+res);
}
}

登入後複製

輸出：

Java 中的二分查找()