## 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.

Pages: 1 2

### 3 Responses to “Ternary Search”

1. Daniel said

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:

\$ c99 -Wall -o ternary_search ternary_search.c

Output:

element: index
0:  0
1:  1
2:  2
3: -1
4:  3
5: -1
6: -1
7:  4
8:  5
9:  6
10:  7
11:  8
12:  9
13: 10
14: -1
15: 11
16: -1
17: 12
18: 13
19: 14

2. Paul said

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

3. […] looked at variants of binary search in two recent exercises. Today we look at a third […]