การค้นหาแบบสามส่วน

เช่นเดียวกับการค้นหาแบบไบนารี มันยังแยกรายการออกเป็นรายการย่อย ขั้นตอนนี้แบ่งรายการออกเป็นสามส่วนโดยใช้ค่ากลางสองตัว เนื่องจากรายการถูกแบ่งออกเป็นส่วนย่อยต่างๆ มากขึ้น จึงช่วยลดเวลาในการค้นหาค่าคีย์

ความซับซ้อนของเทคนิคการค้นหาแบบสามส่วน

• ความซับซ้อนของเวลา:O(log3 n)
• ความซับซ้อนของอวกาศ:O(1)

อินพุตและเอาต์พุต

Input:
A sorted list of data: 12 25 48 52 67 79 88 93
The search key 52
Output:
Item found at location: 3

อัลกอริทึม

ternarySearch(array, start, end, key)

อินพุต - อาร์เรย์ที่จัดเรียง ตำแหน่งเริ่มต้นและสิ้นสุด และแป้นค้นหา

ผลลัพธ์ − ตำแหน่งของกุญแจ (หากพบ) มิฉะนั้น ตำแหน่งที่ไม่ถูกต้อง

Begin
   if start <= end then
      midFirst := start + (end - start) /3
      midSecond := midFirst + (end - start) / 3
      if array[midFirst] = key then
         return midFirst
      if array[midSecond] = key then
         return midSecond
      if key < array[midFirst] then
         call ternarySearch(array, start, midFirst-1, key)
      if key > array[midSecond] then
         call ternarySearch(array, midFirst+1, end, key)
      else
         call ternarySearch(array, midFirst+1, midSecond-1, key)
   else
      return invalid location
End

ตัวอย่าง

#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