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.

Advertisements

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: