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.

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: