資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會研究
時裝研究
法律研究比較二分查詢與順序查詢的C++程式
二分查詢和順序或線性查詢都用在計算機程式設計中以查詢元素。二分查詢的時間複雜度為 O(log(n))，順序查詢的時間複雜度為 O(n)。
演算法
Begin Algorithm for Binary Search: BinarySearch() function with ‘arr’ the array of data and ‘n’ the number of values, start and end index, iteration count and element to be searched in the argument list. Increment iteration counter and compare the item value with the a[mid]. If item < a[mid] choose first half otherwise second half to proceed further. Return iteration value on successful search. End
示例程式碼
#include<iostream>
using namespace std;
int BinarySearch(int a[], int start, int end, int item, int iter) {
int i, mid;
cout<<"\niteration "<<iter+1;
iter++;
mid = start + (end-start+1)/2;
if(item > a[end] || item < a[start] || mid == end) {
cout<<"\nNot found";
return iter;
} else if(item == a[mid]) {
cout<<"\n item found at "<<mid<<" index.";
return iter;
} else if(item == a[start]) {
cout<<"\n item found at "<<start<<" index.";
return iter;
} else if(item == a[end]) {
cout<<"\n item found at "<<end<<" index.";
return iter;
} else if(item > a[mid])
BinarySearch(a, mid, 9, item, iter);
else
BinarySearch(a, start, mid, item, iter);
}
int LinearSearch(int a[], int n, int item) {
int i;
for(i = 0; i < n; i++) {
cout<<"\niteration "<<i+1;
if(a[i] == item) {
cout<<"\n item found at "<<i<<" index.";
return i+1;
}
}
cout<<"\nNot found";
}
int main() {
int n, i, B, L, a[10]={2, 7, 14, 24, 26, 35, 38, 41, 49, 53};
cout<<"\nEnter the element to be searched: ";
cin>>n;
cout<<"\n\n\t\t\tBinary Search :";
B = BinarySearch(a, 0, 9, n, 0);
cout<<"\n\n\t\t\tLinear Search :";
L = LinearSearch(a, 10, n);
if(L > B)
cout<<"\n\nBinary search is better for this search.";
else if(L < B)
cout<<"\n\nLinear search is better for this search.";
else
cout<<"\n\nBoth are equally efficient for this search.";
return 0;
}輸出
Enter the element to be searched: 7 Binary Search : iteration 1 iteration 2 iteration 3 iteration 4 item found at 1 index. Linear Search : iteration 1 iteration 2 item found at 1 index. Linear search is better for this search. Enter the element to be searched: 53 Binary Search : iteration 1 item found at 9 index. Linear Search : iteration 1 iteration 2 iteration 3 iteration 4 iteration 5 iteration 6 iteration 7 iteration 8 iteration 9 iteration 10 item found at 9 index. Binary search is better for this search. Enter the element to be searched: 1 Binary Search : iteration 1 Not found Linear Search : iteration 1 iteration 2 iteration 3 iteration 4 iteration 5 iteration 6 iteration 7 iteration 8 iteration 9 iteration 10 Not found Binary search is better for this search.
更新於：2019-07-30
503次瀏覽
廣告