資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中的二分查詢
二分查詢是一種透過反覆將已排序陣列減半來查詢所需元素的方法。
此方法從整個陣列開始。然後將其減半。如果所需資料值大於陣列中間的元素，則考慮陣列的上半部分。否則，考慮下半部分。持續進行此操作，直到獲得所需資料值或剩餘陣列為空。
下面給出了一個演示C++中二分查詢的程式。
示例
#include
using namespace std;
int binarySearch(int arr[], int p, int r, int num) {
if (p <= r) {
int mid = (p + r)/2;
if (arr[mid] == num)
return mid ;
if (arr[mid] > num)
return binarySearch(arr, p, mid-1, num);
if (arr[mid] < num)
return binarySearch(arr, mid+1, r, num);
}
return -1;
}
int main(void) {
int arr[] = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int num;
cout << "Enter the number to search: \n";
cin >> num;
int index = binarySearch (arr, 0, n-1, num);
if(index == -1){
cout<< num <<" is not present in the array";
}else{
cout<< num <<" is present at index "<< index <<" in the array";
}
return 0;
}輸出
Enter the numberto search 20 20 is present at index 5 in the array
在上面的程式中，`binarySearch()`是一個遞迴函式，用於使用二分查詢在陣列中查詢所需元素。該函式將陣列、其下界和上界以及要查詢的數字作為引數。如下所示。
int binarySearch(int arr[], int p, int r, int num)
然後計算陣列的中點。如果中點的值等於num，則返回它。如果值大於num，則陣列將自身遞迴呼叫，下界為p，上界為mid-1。如果值小於num，則陣列將自身遞迴呼叫，下界為mid+1，上界為r。這可以透過以下程式碼片段看到。
int binarySearch(int arr[], int p, int r, int num) {
if (p <= r) {
int mid = (p + r)/2;
if (arr[mid] == num)
return mid ;
if (arr[mid] > num)
return binarySearch(arr, p, mid-1, num);
if (arr[mid] < num)
return binarySearch(arr, mid+1, r, num);
}
return -1;
}在`main()`函式中，定義了陣列`arr[]`。計算陣列的大小並指定要查詢的數字。然後呼叫`binarySearch()`來查詢數字的索引。如果`binarySearch()`返回的值為-1，則該數字不在陣列中。否則，返回索引值。如下所示。
int main(void) {
int arr[] = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int num = 33;
int index = binarySearch (arr, 0, n-1, num);
if(index == -1)
cout<< num <<" is not present in the array";
else
cout<< num <<" is present at index "<< index <<" in the array";
return 0;
}
更新於：2021年6月28日
18K+ 瀏覽量
廣告