Floor And Ceiling In An Array
November 21, 2017
We looked at variants of binary search in two recent exercises. Today we look at a third variant.
Your task is to write a variant of binary search in a sorted array without duplicates that returns the index of the two elements immediately below and above a target; if the target is in the array, both return values should point to the target value. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
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: