November 21, 2017 10:00 AM
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.
Posted by programmingpraxis
Categories: Exercises
Tags:
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.
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)By chaw on November 21, 2017 at 3:43 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))By Pascal Bourguignon on November 21, 2017 at 7:02 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:
By Daniel on December 2, 2017 at 8:48 PM