数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会科学
时尚研究
法律研究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.
更新时间： 30-7 月-2019
408 浏览量
广告