資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Java二分查詢程式
二分查詢是一種快速的查詢演算法，其執行時間複雜度為O(log n)。該演算法基於分治法的原理。為了使該演算法正常工作，資料集合必須已排序。
二分查詢透過比較集合中最中間的項來查詢特定項。如果找到匹配項，則返回該項的索引。如果中間項大於該項，則在中間項左側的子陣列中搜索該項。否則，在中間項右側的子陣列中搜索該項。此過程也繼續在子陣列上進行，直到子陣列的大小減小到零。
二分查詢演算法
以下是實現二分查詢演算法的步驟：
- 選擇陣列中的中間項，並將其與要搜尋的關鍵值進行比較。如果匹配，則返回中間項的位置。
- 如果不匹配關鍵值，請檢查關鍵值是否大於或小於中間值。
- 如果關鍵值更大，則在右子陣列中執行搜尋；但如果關鍵值小於中間值，則在左子陣列中執行搜尋。
- 迭代地重複步驟1、2和3，直到子陣列的大小變為1。
- 如果關鍵值不存在於陣列中，則演算法返回搜尋失敗。
虛擬碼
以下是二分查詢演算法的虛擬碼：
Procedure binary_search
A ← sorted array
n ← size of array
x ← value to be searched
Set lowerBound = 1
Set upperBound = n
while x not found
if upperBound < lowerBound
EXIT: x does not exists.
set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
if A[midPoint] < x
set lowerBound = midPoint + 1
if A[midPoint] > x
set upperBound = midPoint - 1
if A[midPoint] = x
EXIT: x found at location midPoint
end while
end procedure
Java二分查詢程式
以下是使用Java實現二分查詢演算法的程式碼：
public class BinarySearch {
public static void main(String args[]){
int array[] = {10, 20, 25, 57, 63, 96};
int size = array.length;
int low = 0;
int high = size-1;
int value = 25;
int mid = 0;
mid = low +(high-low)/2;
while(low<=high){
if(array[mid] == value){
System.out.println(mid);
break;
}
else if(array[mid]<value)
low = mid+1;
else high = mid - 1;
}
mid = (low+high)/2;
}
}
輸出
2
程式碼解釋
這個Java程式在一個已排序的陣列上執行二分查詢，以查詢特定值的索引。它初始化低索引和高索引，計算中間索引，並進入一個迴圈來將中間索引處的值與搜尋值進行比較。迴圈調整低索引和高索引，直到找到搜尋值，然後列印中間索引。該程式使用二分查詢演算法有效地查詢索引。
更新於：2024年7月26日
2K+ 瀏覽量
廣告