C ++程序，用于为特定搜索序列实现二进制搜索算法
在此程序中，我们需要实现二进制搜索以找到数组中搜索序列的存在。二进制搜索的时间复杂度为O（log(n)）。
所需步骤和伪代码
Begin BinarySearch() function has ‘arr’ the array of data and ‘n’ the number of values, start and end index, iteration count and b[0] be the element to be searched in the argument list. Increment the 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 index value to main. In main(), sequentially compare the remaining items of search sequence to next items in the array. Print the index range of the sequence found. End.
范例程式码
#include<iostream>
using namespace std;
int BinarySearch(int a[], int start, int end, int item, int iter) {
int i, mid;
iter++;
mid = start+ (end-start+1)/2;
if(item > a[end] || item < a[start] || mid == end) {
cout<<"\nNot found";
return -1;
} else if(item == a[mid]) {
return mid;
} else if(item == a[start]) {
return start;
} else if(item == a[end]) {
return end;
} else if(item > a[mid])
BinarySearch(a, mid, end, item, iter);
else
BinarySearch(a, start, mid, item, iter);
}
int main() {
int n, i, flag=0, Bin, len = 9, a[10]={1, 7, 15, 26, 29, 35, 38, 40, 49, 51};
cout<<"\nEnter the number of element in the search sequence: ";
cin>>n;
int b[n];
for(i = 0; i < n; i++) {
cin>>b[i];
}
Bin = BinarySearch(a, 0, len, b[0], 0);
if (Bin == -1) {
cout<<"\nNot found.";
return 0;
} else {
for(i = Bin; i < n+Bin; i++)
if(a[i] != b[i-Bin])
flag = 4;
if(flag == 4)
cout<<"\nNot found.";
else
cout<<"\nSequence found between index "<<Bin<<" and "<<Bin+n<<".";
}
return 0;
}输出结果
Enter the number of element in the search sequence: 4 15 26 29 35 Sequence found between index 2 and 6.
热门推荐
10 八一幼儿祝福语大全简短
11 公司乔迁食堂祝福语简短
12 婚礼结束聚餐祝福语简短
13 儿媳买车妈妈祝福语简短
14 毕业送礼老师祝福语简短
15 同事辞职正常祝福语简短
16 恭贺新婚文案祝福语简短
17 金店立秋祝福语简短英文
18 婆婆高寿祝福语大全简短