Programming Praxis

3 Responses to “Floor And Ceiling In An Array”

1. chaw said

   November 21, 2017 at 3:43 PM

   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)
   
2. Pascal Bourguignon said

   November 21, 2017 at 7:02 PM

   
   ;; 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))
   
   
3. Daniel said

   December 2, 2017 at 8:48 PM

   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:

   val below above
     0    -1     0
     1     0     0
     2     0     1
     3     0     1
     4     1     1
     5     2     2
     6     3     3
     7     3     4
     8     4     4
     9     4     5