Ternary Search
November 10, 2017
We looked at binary search in the previous exercise. Today we look at ternary search. Instead of one mid at the middle of the array, ternary search has two mids a third of the way from each end; two-thirds of the array is discarded at each recursive step.
Your task is to write a program that performs ternary search. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Here’s a solution in C99.
/* ternary_search.c */ #include <stdio.h> int search(int* array, int n, int element) { int lo = 0; int hi = n; while (hi > lo) { int addend = (hi - lo) / 3; int mid1 = lo + addend; int val1 = array[mid1]; int mid2 = mid1 + addend; int val2 = array[mid2]; if (val1 == element) return mid1; if (val2 == element) return mid2; if (val1 > element) { hi = mid1; } else if (val2 < element) { lo = mid2 + 1; } else { lo = mid1 + 1; hi = mid2; } } return -1; } int main(void) { int array[] = {0,1,2,4,7,8,9,10,11,12,13,15,17,18,19}; int n = sizeof(array) / sizeof(int); printf("element: index\n"); for (int i = 0; i < 20; ++i) { int idx = search(array, n, i); printf("%d: %2d\n", i, idx); } }Build:
Output:
Like in the Python bisect module I have implemented a trisect_left, which finds an insert point for x. If x is already in the array the new x will be inserted at the left. Then tsearch_left will use trisect_left and find x, if it is there.
def trisect_left(arr, x): 'find insert point for x - if x is already in the array, insert left' n = len(arr) lo, hi = 0, n while lo < hi: delta = (hi - lo) // 3 i1 = lo + delta if arr[i1] < x: lo = i1 + 1 else: hi = i1 continue i2 = hi - delta if arr[i2] < x: lo = i2 + 1 else: hi = i2 return lo def tsearch_left(arr, x): i = trisect_left(arr, x) if i != len(arr) and arr[i] == x: return i return -1[…] looked at variants of binary search in two recent exercises. Today we look at a third […]