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.

Advertisements

Pages: 1 2

3 Responses to “Floor And Ceiling In An Array”

  1. chaw said

    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. 
    ;; 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

    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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: