Binary Search
March 23, 2009
Our binary search sets the variables lo
and hi
to the two ends of the vector, and maintains the invariant that if the target number is present, it must be between lo
and hi
; if lo
ever exceeds hi
, we report that the target number is not present. Otherwise, we calculate the mid-point of the vector and make a three-way decision: if the number at the mid-point is the target number, we report success, otherwise we loop on the appropriate sub-vector:
(define (bsearch t vs)
(let loop ((lo 0) (hi (- (vector-length vs) 1)))
(if (< hi lo) -1
(let ((mid (quotient (+ lo hi) 2)))
(cond ((< t (vector-ref vs mid))
(loop lo (- mid 1)))
((< (vector-ref vs mid) t)
(loop (+ mid 1) hi))
(else mid))))))
Our test generates two types of vectors and tests each for all sizes from zero to a user-requested limit. The first vector has the integers from 0 to limit-1, and tests each number from 0 to limit-1 for a successful search, plus the two fractions 1/2 above and below each number from 0 to limit-1 for unsuccessful search. The first vector has all elements set to 1, and searches for 1 for a successful search and 1/2 and 3/2 for an unsuccessful search.
Assert
is a macro that compares its two arguments and reports if they are not equal; the message includes the text of the expression, making it easy to see what failed. Range
returns a list of non-negative integers less than n. Both appear in the Standard Prelude.
(define (test-search limit)
(do ((n 0 (+ n 1))) ((= n limit))
(let ((in-order (list->vector (range n)))
(all-equal (make-vector n 1)))
(do ((i 0 (+ i 1))) ((= i n))
(assert (bsearch i in-order) i)
(assert (bsearch (+ i 1/2) in-order) -1)
(assert (bsearch (- i 1/2) in-order) -1))
(assert (bsearch 1/2 all-equal) -1)
(assert (bsearch 3/2 all-equal) -1)
(if (positive? n) (assert (< -1 (bsearch1 all-equal) n) #t)))))
Performing the test shows that all is well:
> (test-search 12)
>
This solution is available at http://programmingpraxis.codepad.org/UxAnLcJF.
Hm, it seems fairly trivial, but given the description I’m undoubtedly missing something. Anyway, here’s my attempt in Haskell:
Please be more specific: since the array is nondecreasing, there might be more than one element having the same value. Which index should the function return? Is the index of any element having the target value acceptable, or should it be the index of the first, or the last, or something else?
You may assume all elements of the array are distinct.
[…] terrestrial television programme services of Asia Television Limited (ATV) (Note 1). … Binary Search « Programming Praxis – programmingpraxis.wordpress.com 03/23/2009 Jon Bentley, in his book Programming Pearls, reports […]
Sorry long post as I included fairly exhaustive test conditions using schemeunit. There are several edge cases with a binary search so I thought I’d include tests for all the ones I thought of.
barryallison,
What test cases would you use to test the following algorithms
1.) insertion sort
2.) mergesort
3.) heapsort
4.) binary trees methods (e.g. insert, delete, etc.)
In Python,
my c solution
int binary_search(int arr[], int n, int key)
{
int left, right, mid;
left = 0;
right = n – 1;
while(right > left)
{
mid = (left + right)/2;
if(key arr[mid])
{
left = mid + 1;
}
else
return mid;
}
return -1;
}
[\sourcecode]
My c solution
ruby solution (http://codepad.org/jUgepFQa) Doesn’t exactly use the binary chop *shameface*
Another interesting binary search algorithm that creates the binary representation of the position at which the targeted value can be found:
https://github.com/ftt/programming-praxis/blob/master/20090323-binary-search/binary-search.py