Ternary Search

Like the binary search, it also separates the lists into sub-lists. This procedure divides the list into three parts using two intermediate mid values. As the lists are divided into more subdivisions, so it reduces the time to search a key value.

The complexity of Ternary Search Technique

• Time Complexity: O(log3 n)
• Space Complexity: O(1)

Input and Output

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

Algorithm

ternarySearch(array, start, end, key)

Input − An sorted array, start and end location, and the search key

Output − location of the key (if found), otherwise wrong location.

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

Example

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

Output

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