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

Posted by programmingpraxis
Filed in Exercises
3 Comments »

3 Responses to “Ternary Search”

  1. Daniel said
    November 10, 2017 at 2:31 PM

    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
    November 11, 2017 at 10:23 AM

    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. Floor And Ceiling In An Array | Programming Praxis said
    November 21, 2017 at 10:01 AM

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

Leave a comment