資料結構
網路
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 瀏覽量
廣告