Floor And Ceiling In An Array
November 21, 2017
Here is our solution. We first check the two ends of the array, which are special cases because the return values are outside the ends of the array. Then we do a standard binary search, returning the index of the target if it appears in the array or the index of the hi and lo indices if the target does not appear in the array:
(define (floor-ceiling lt? x xs)
(let* ((len (vector-length xs)) (len-1 (- len 1)))
(if (lt? x (vector-ref xs 0)) (list -1 0)
(if (lt? (vector-ref xs (- len 1)) x) (list len-1 len)
(let loop ((lo 0) (hi len-1))
(let ((mid (+ lo (quotient (- hi lo) 2))))
(cond ((< hi lo) (list hi lo))
((lt? x (vector-ref xs mid)) (loop lo (- mid 1)))
((lt? (vector-ref xs mid) x) (loop (+ mid 1) hi))
(else (list mid mid)))))))))
Here is a test program. I had more trouble getting this right than the binary search:
(define (test)
(do ((x 0 (+ x 1))) ((= x 50))
(let ((fc (floor-ceiling < x xs)) (len (vector-length xs)))
(when (< (cadr fc) (car fc))
(display "what? ") (display x) (display " ") (display fc) (newline))
(if (= (cadr fc) len)
(when (not (< (vector-ref xs (- len 1)) x))
(display "bad ceiling ") (display x) (display " ") (display fc) (newline))
(when (< (vector-ref xs (cadr fc)) x)
(display "bad ceiling ") (display x) (display " ") (display fc) (newline)))
(if (= (car fc) -1)
(when (not (< x (vector-ref xs 0)))
(display "bad floor ") (display x) (display " ") (display fc) (newline))
(when (< x (vector-ref xs (car fc)))
(display "bad floor ") (display x) (display fc) (newline))))))
You can run the program at https://ideone.com/zfN2jq.
The design is based on the predicates in the comments.
(import (scheme base) (scheme write)) (define (binary-search-duo key vec lt?) (define-syntax v (syntax-rules () ((_ i) (vector-ref vec i)))) (define (bsearch lo hi) (if (< (- hi lo) 2) (list lo hi) (let* ((mid (quotient (+ lo hi) 2)) ; lo < mid < hi (vmid (vector-ref vec mid))) (cond ((lt? vmid key) (bsearch mid hi)) ((lt? key vmid) (bsearch lo mid)) (else (list mid mid)))))) (let ((hi (- (vector-length vec) 1))) (cond ((negative? hi) (list #f #f)) ;; 0 <= hi < n ((lt? key (v 0)) (list #f 0)) ((not (lt? (v 0) key)) (list 0 0)) ((lt? (v hi) key) (list hi #f)) ((not (lt? key (v hi))) (list hi hi)) ;; (v 0) < key < (v hi) (else (bsearch 0 hi))))) (define (test) (let ((tvec '#(5 7 11 23 24 25 37 42 43 89 99))) (vector-for-each (lambda (v) (display (binary-search-duo v tvec <)) (newline)) tvec) (for-each (lambda (v) (display (binary-search-duo v tvec <)) (newline)) '(6 14 0 101)))) (test);; This is when you're happy to have in your library a well defined ;; generic operation. So you don't have to re-implement and re-debug ;; it each time, and so that this kind of user request changes are ;; trivial to implement. Notice also that as usual, the customer make ;; ludicruous demands, such as having two indexes when it's obviously ;; not possible when the target outside of the vector. We'll return a ;; NIL in place of the missing index. (defun binary-search-floor-ceiling (vector value compare &key (start 0) (end (length vector)) (key (function identity))) " COMPARE: A comparing two elements A and B, and returning an order (signed integer), such as: A<B <=> result<0 A=B <=> result=0 A>B <=> result>0 START: The minimum index. END: The maximum index+1. RETURN: (values index-floor index-ceiling) " (multiple-value-bind (found index order) (com.informatimago.common-lisp.cesarum.utility:dichotomy-search vector value compare :start start :end end :key key) (cond (found (values index index)) ((minusp order) (values nil start)) ((= index (1- end)) (values (1- end) nil)) (t (values index (1+ index)))))) (loop with vector = #(1 3 5 7 9) for target from 0 to 10 collect (multiple-value-list (binary-search-floor-ceiling vector target (lambda (a b) (cond ((< a b) -1) ((> a b) +1) (t 0)))))) ;; --> ((nil 0) (0 0) (0 1) (1 1) (1 2) (2 2) (2 3) (3 3) (3 4) (4 4) (4 nil))Here’s a solution in C99.
/* search.c */ #include <stdio.h> #include <stdbool.h> void search(int* array, int n, int target, int* below, int* above) { int lo = -1; int hi = n; bool success = false; int mid; while (hi > lo + 1) { mid = lo + (hi-lo)/2; int val = array[mid]; if (val == target) { success = true; break; } else if (val > target) { hi = mid; } else { lo = mid; } } if (success) { *below = *above = mid; } else { *below = lo; *above = hi; } } int main(void) { int array[] = {1, 4, 5, 6, 8}; int n = sizeof(array) / sizeof(int); printf("val below above\n"); for (int target = 0; target < 10; ++target) { int below; int above; search(array, n, target, &below, &above); printf("%3d %5d %5d\n", target, below, above); } }Build and run:
Output: