الگوریتم جستجوی سه گانه (Ternary Search)

الگوریتم جستجوی سه گانه (Ternary Search)

در این بخش الگوریتم جستجوی سه گانه (Ternary Search) را بررسی خواهیم کرد. این الگوریتم مانند الگوریتم Binary Search است با این تقاوت که آرایه به سه قسمت تقسیم می کند و دو مقدار را به عنوان مقادیر وسط در نظر میگیرد. از آنجا که در مرحله یک آرایه به سه آرایه تقسیم می شود، زمانی جستجو نیز کاهش می یابد.

مسئله

با توجه به آرایه مرتب داده شده (arr[])، تابعی بنویسید که عنصر x را در آرایه جستجو کند.

ورودی – خروجی

Input:
arr[]: 12 25 48 52 67 79 88 93
X: 52
Output:
Item found at location: 3

مثال

پیاده سازی الگوریتم جستجوی سه گانه با زبان سی پلاس پلاس:

#include<iostream>
using namespace std;
int ternarySearch(int array[], int start, int end, int key) {
   if(start <= end) {
      int midFirst = (start + (end - start) /3); //mid of first and second block
      int midSecond = (midFirst + (end - start) /3); //mid of first and second block
      if(array[midFirst] == key)
         return midFirst;
      if(array[midSecond] == key)
         return midSecond;
      if(key < array[midFirst])
         return ternarySearch(array, start, midFirst-1, key);
      if(key > array[midSecond])
         return ternarySearch(array, midSecond+1, end, key);
      return ternarySearch(array, midFirst+1, midSecond-1, key);
   }
   return -1;
}
int main() {
   int n, searchKey, loc;
   cout << "Enter number of items: ";
   cin >> n;
   int arr[n]; //create an array of size n
   cout << "Enter items: " << endl;
   for(int i = 0; i< n; i++) {
      cin >> arr[i];
   }
   cout << "Enter search key to search in the list: ";
   cin >> searchKey;
   if((loc = ternarySearch(arr, 0, n, searchKey)) >= 0)
      cout << "Item found at location: " << loc << endl;
   else
      cout << "Item is not found in the list." << endl;
}

امتحان کنید

خروجی:

Enter number of items: 8
Enter items:
12 25 48 52 67 79 88 93
Enter search key to search in the list: 52
Item found at location: 3

نکات

• پیچیدگی زمانی این الگوریتم برابر با O(log3 n) است.
• فضای موقت برابر با O(1) است.

نوشته الگوریتم جستجوی سه گانه (Ternary Search) اولین بار در سورس سرا - آموزش برنامه نویسی. پدیدار شد.