## Ternary Search

### November 10, 2017

We begin with the binary search from the previous exercise. It is instructive to compare binary search to ternary search, and having a binary search gives us a useful tool for testing:

```(define (bsearch lt? x xs)
(let loop ((lo 0) (hi (- (vector-length xs) 1)))
(let ((mid (+ lo (quotient (- hi lo) 2))))
(cond ((< hi lo) #f)
((lt? x (vector-ref xs mid)) (loop lo (- mid 1)))
((lt? (vector-ref xs mid) x) (loop (+ mid 1) hi))
(else mid)))))```

Our ternary search performs four comparisons per recursive step instead of two; even though there are fewer recursive steps, each does more work, and it is not clear that ternary search provides any savings over binary search:

```(define (tsearch lt? x xs)
(let loop ((lo 0) (hi (- (vector-length xs) 1)))
(let ((lomid (+ lo (quotient (- hi lo) 3)))
(himid (- hi (quotient (- hi lo) 3))))
(cond ((< hi lo) #f)
((lt? x (vector-ref xs lomid)) (loop lo (- lomid 1)))
((lt? (vector-ref xs himid) x) (loop (+ himid 1) hi))
((not (lt? (vector-ref xs lomid) x)) lomid)
((not (lt? x (vector-ref xs himid))) himid)
(else (loop (+ lomid 1) (- himid 1)))))))```

Here are some examples:

```> (define xs '#(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47))
> (bsearch < 7 xs)
3
> (bsearch < 14 xs)
#f
> (tsearch < 7 xs)
3
> (tsearch < 14 xs)
#f
> (tsearch < 37 xs)
11
> (tsearch < 45 xs)
#
> (do ((x 1 (+ x 1))) ((= x 50) 'okay)
(assert (bsearch < x xs) (tsearch <x xs)))
okay```

You can run the program at https://ideone.com/RnwQzb.

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 […]