How to write the Ternary Search alogrithm?

Question

Algorithm that searches a sorted list of n items by dividing it into three sublists of almost n/3 items. This algorithm finds the sublist that might contain the given item and divides it into three smaller sublists of almost equal size. The algorithm repeats this process until it finds the item or concludes that the item is not in the list

Answer 1

What you've described there is called Ternary Searching Algorithm, it is similar to Binary search, except we're dividing the collection into three subsets. Here is an explanation in C++:

// Function to perform Ternary Search
int ternarySearch(int l, int r, int key, int ar[])
{
    if (r >= l) {
 
        // Find the mid1 and mid2
        int mid1 = l + (r - l) / 3;
        int mid2 = r - (r - l) / 3;
 
        // Check if key is present at any mid
        if (ar[mid1] == key) {
            return mid1;
        }
        if (ar[mid2] == key) {
            return mid2;
        }
 
        // Since key is not present at mid,
        // check in which region it is present
        // then repeat the Search operation
        // in that region
        if (key < ar[mid1]) {
 
            // The key lies in between l and mid1
            return ternarySearch(l, mid1 - 1, key, ar);
        }
        else if (key > ar[mid2]) {
 
            // The key lies in between mid2 and r
            return ternarySearch(mid2 + 1, r, key, ar);
        }
        else {
 
            // The key lies in between mid1 and mid2
            return ternarySearch(mid1 + 1, mid2 - 1, key, ar);
        }
    }
 
    // Key not found
    return -1;
}
 
// Driver code
int main()
{
    int l, r, p, key;
 
    // Get the array
    // Sort the array if not sorted
    int ar[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
 
    // Starting index
    l = 0;
 
    // length of array
    r = 9;
 
    // Checking for 5
 
    // Key to be searched in the array
    key = 5;
 
    // Search the key using ternarySearch
    p = ternarySearch(l, r, key, ar);
 
    // Print the result
    cout << "Index of " << key
         << " is " << p << endl;
 
    // Checking for 50
 
    // Key to be searched in the array
    key = 50;
 
    // Search the key using ternarySearch
    p = ternarySearch(l, r, key, ar);
 
    // Print the result
    cout << "Index of " << key
         << " is " << p << endl;
}