## 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 `mid`s 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 […]