比较二进制和顺序搜索的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 战友聚会祝福语幽默简短
17 最新中秋祝福语简短英语
18 夏日升学宴祝福语简短
