Python Program for Ternary Search

What is ternary search ?

• Similarly like linear search and binary search, ternary search is a searching technique that is used to find the index or position of a particular value in collection of elements.
• Ternary search is used only on a sorted collection of elements.
• Ternary search, like binary search, is based on divide-and-conquer algorithm.
• it is divided into 3 parts (where in binary search 2 parts) and then determines in which part the element exists.

Example, consider sorted collection of elements

Ternary Search Time complexity

Ternary Search Python Program

#!/usr/bin/python                                                               
                                                                                
def ternary_search(left_index, right_index, search_key, list_vals):             
    if (right_index >= left_index):                                             
        mid_index1 = left_index + (right_index -left_index)/3;                  
        mid_index2 = right_index - (right_index - left_index)/3;                
        if (list_vals[mid_index1] == search_key):                               
            return mid_index1;                                                  
        if (list_vals[mid_index2] == search_key):                               
            return mid_index2;                                                  
                                                                                
        if (search_key < list_vals[mid_index1]):                                
            return ternary_search(left_index,mid_index1-1, search_key, list_vals);
        elif (search_key > list_vals[mid_index2]):                              
            return ternary_search(mid_index2+1, right_index, search_key, list_vals);
        else:                                                                   
            return ternary_search(mid_index1+1, mid_index2-1, search_key, list_vals);
    return -1;                                                                  
                                                                                
if __name__ == "__main__":                                                      
    list_vals = [10, 20, 30, 40, 50, 60, 70, 80];                               
    key = int(raw_input("Please enter a string:"));                             
    left_index = 0;                                                             
    right_index = len(list_vals);                                               
    print("key is found at index: %d" % ternary_search(left_index, right_index, key, list_vals));                                                           

$ python ternary-search.py 
Please enter a string:30
key is found at index: 2
$ 50
$ python ternary-search.py 
Please enter a string:50
key is found at index: 4
$ python ternary-search.py 
Please enter a string:20
key is found at index: 1
$ python ternary-search.py 
Please enter a string:9
key is found at index: -1