이진 검색과 순차 검색을 비교하는 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.