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

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
```