比较二进制和顺序搜索的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.
热门推荐
10 水晶婚夫妻祝福语简短
11 收围巾的祝福语简短
12 简短有力的结婚祝福语
13 创业大吉祝福语简短
14 送给客户的祝福语 简短
15 贺卡祝福语情侣搞笑简短
16 60岁长辈祝福语简短
17 七一祝福语明信片文案简短
18 朋友节最简短祝福语