Chương trình C ++ để triển khai thuật toán tìm kiếm nhị phân cho chuỗi tìm kiếm cụ thể

Trong Chương trình này, chúng ta cần thực hiện tìm kiếm nhị phân để tìm sự tồn tại của một chuỗi tìm kiếm trong một mảng. Độ phức tạp về thời gian của tìm kiếm nhị phân là O (log (n)).

Các bước bắt buộc và mã giả

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.

Mã mẫu

#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;
}

Đầu ra

Enter the number of element in the search sequence: 4
15
26
29
35
Sequence found between index 2 and 6.