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