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.
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:
Output:
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[…] looked at variants of binary search in two recent exercises. Today we look at a third […]