Python Tutorial

# 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 performs the search operation on the other 2/3 parts in every steps. this results in a worst case time complexity of O(log3N), where N is the number of elements in the collection.

## 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));
```
Output:
```\$ python ternary-search.py
key is found at index: 2
\$ 50
\$ python ternary-search.py
key is found at index: 4
\$ python ternary-search.py
key is found at index: 1
\$ python ternary-search.py
key is found at index: -1
```

Python Tutorial