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.

About these ads

Pages: 1 2

13 Responses to “Binary Search”

  1. FalconNL said

    Hm, it seems fairly trivial, but given the description I’m undoubtedly missing something. Anyway, here’s my attempt in Haskell:

    import Data.List
    import qualified Data.Sequence as S
    import Test.QuickCheck
    
    main = quickCheck prop_bsearch
    
    bsearch :: Int -> S.Seq Int -> Maybe Int
    bsearch n s | s == S.empty = Nothing
                | i == n       = Just x
                | i > n        = bsearch n $ S.take x s
                | otherwise    = fmap (x + 1 +) (bsearch n $ S.drop (x + 1) s)
                where i = S.index s x
                      x = div (S.length s) 2
    
    prop_bsearch n [] = bsearch n (S.fromList []) == Nothing
    prop_bsearch n s  = maybe (notElem n s) ((== n) . (sort s !!)) . bsearch n . S.fromList $ sort s
    
  2. A. Nonymous said

    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?

  3. programmingpraxis said

    You may assume all elements of the array are distinct.

  4. [...] 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 [...]

  5. barryallison said

    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.

    (define (bsearch target items)
      (let scan ([lower 0] 
                 [upper (sub1 (vector-length items))])
        (if (> lower upper) 
            -1
            (let* ([mid (quotient (+ upper lower) 2)]
                   [mid-item (vector-ref items mid)])
              (cond 
                [(< target mid-item) (scan lower (sub1 mid))]
                [(> target mid-item) (scan (add1 mid) upper)]
                [else mid])))))
    
    
    (require (planet schematics/schemeunit:3:4))
    
    (define empty-set       #())
    (define single-item-set #(1))
    (define odd-size-set    #(11 12 23 34 45 56 67))
    (define even-size-set   #(11 12 23 34 45 56 67 78))
    (define all-equal-set   #(11 11 11 11 11))
    (define *not-found* -1)
    
    (define bsearch-tests
      (test-suite
       "Tests for bsearch.ss"
       
       (test-case "Base sets"
                  (check-equal? (bsearch 3  empty-set)       *not-found*) ; empty set fails 
                  (check-equal? (bsearch 3  single-item-set) *not-found*) ; single element fail
                  (check-equal? (bsearch 1  single-item-set) 0)           ; find single element
                  )
       
       (test-case "Odd number of elements"
                  (check-equal? (bsearch 11  odd-size-set) 0) ; find first item 
                  (check-equal? (bsearch 45  odd-size-set) 4) ; find some item
                  (check-equal? (bsearch 34  odd-size-set) 3) ; find exact mid item 
                  (check-equal? (bsearch 67  odd-size-set) 6) ; find last item
                  (check-equal? (bsearch 1   odd-size-set) *not-found*) ; fail low
                  (check-equal? (bsearch 102 odd-size-set) *not-found*) ; fail high
                  (check-equal? (bsearch 36  odd-size-set) *not-found*) ; fail mid-way
                  )
       
       (test-case "Even number of elements"
                  (check-equal? (bsearch 11  even-size-set) 0)  ; find first item 
                  (check-equal? (bsearch 45  even-size-set) 4)  ; find some item
                  (check-equal? (bsearch 34  even-size-set) 3)  ; find exact mid item 
                  (check-equal? (bsearch 78  even-size-set) 7)  ; find last item
                  
                  (check-equal? (bsearch 10  even-size-set) *not-found*)  ; fail low
                  (check-equal? (bsearch 102 even-size-set) *not-found*)  ; fail high
                  (check-equal? (bsearch 36  even-size-set) *not-found*)  ; fail mid-way
                  )
       
       (test-case "Identical elements set"
                  (check-not-equal? (bsearch 11  even-size-set) *not-found*) ; finds first item 
                  (check-equal?     (bsearch 10  all-equal-set) *not-found*) ; fail low
                  (check-equal?     (bsearch 12  all-equal-set) *not-found*) ; fail high
                  )
       ))
    
    (require (planet schematics/schemeunit:3/text-ui))
    (run-tests bsearch-tests 'normal)
  6. Chris said

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

  7. Jebb said

    In Python,

    #!/usr/bin/python
    
    def binsearch(n, ordList):
    	first = 0
    	last = len(ordList)
    	while last > first:
    		#print "range %s - %s" % (first, last)	#Uncomment for debugging
    		m = first + (last - first) / 2
    		#print "middle %s" % m	#Uncomment for debugging
    		if ordList[m] == n:
    			return m
    		elif ordList[m] < n:
    			first = m + 1
    		elif ordList[m] > n:
    			last = m
    	return -1
    
    def testsearch(f):
    	testarray = [(1, [], -1),
    	             (1, [0], -1),
    	             (4, [1, 2, 3, 4, 5, 6, 7], 3),
    	             (4, [1, 2, 3, 4, 5, 6, 7, 12], 3),
    	             (4, [1, 3, 5, 7], -1),
    	             (4, [1, 3, 5, 7, 12], -1),
    	             (10, [0, 1, 5, 7, 10], 4),
    	             (10, [0, 1, 5, 7, 9, 10], 5),
    	             (1, [1, 3, 5, 7, 8], 0),
    	             (4, [5, 5, 7, 8], -1),
    	             (6, [1, 2, 4, 5], -1)]
    	for (x, L, position) in testarray:
    		check = binsearch(x, L) == position
    		print check
    		if check == False:
    			print "%s in %s at %s" % (str (x), str(L), str(position))
    		print
    
    if __name__ == '__main__':
    	testsearch(binsearch)
    
  8. Vikas Tandi said

    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]

  9. Vikas Tandi said

    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])
    		{
    			right = mid - 1;
    		}
    		else if(key > arr[mid])
    		{
    			left = mid + 1;
    		}
    		else
    			return mid;
    	}
    
    	return -1;
    }
    
  10. swaraj said

    ruby solution (http://codepad.org/jUgepFQa) Doesn’t exactly use the binary chop *shameface*

  11. cosmin said

    Another interesting binary search algorithm that creates the binary representation of the position at which the targeted value can be found:

    def binary_search(a, value):
    	n, i, pow2 = len(a), 0, 1
    	while pow2 < n: pow2 <<= 1
    	while pow2:
    		if (i | pow2) < n and a[i | pow2] <= value:
    			i |= pow2
    		pow2 >>= 1
    	return i if a[i] == value else None
    
    def test():
    	assert binary_search([0, 1, 2, 3, 4, 5, 6, 7], 3) == 3
    	assert binary_search([0, 1, 2, 3, 4, 5, 6, 7], 6) == 6
    	assert binary_search([0, 1, 2, 3, 4, 5, 6, 7], 5) == 5
    	assert binary_search([0, 1, 2, 3, 4, 5, 6], 5) == 5
    	assert binary_search([0, 1, 2, 3, 4, 5, 6], 4) == 4
    	assert binary_search([0, 1, 2, 3, 4, 5, 6], 7) == None
    	assert binary_search([0, 1, 2, 3, 4, 5], -1) == None
    
    test()
    
  12. Lucas A. Brown said
    #! /usr/bin/env python
    
    def binsearch(l, x):
        lower, upper = 0, len(l)-1
        if l[upper] == x: return upper
        while True:
            mid = (lower + upper) / 2
            if l[mid] == x: return mid
            elif l[mid] < x: lower = mid
            else:            upper = mid
    
    if __name__ == "__main__":
        from random import sample
        for x in xrange(100):
            l = sample(xrange(100), 25)
            l.sort()
            assert binsearch(l, l[x/4]) == l.index(l[x/4])
    

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

Follow

Get every new post delivered to your Inbox.

Join 627 other followers

%d bloggers like this: