## Binary Search

### March 23, 2009

Children who are learning arithmetic sometimes play a number-guessing game: “I’m thinking of a number between 1 and 100. Can you guess it?” “Is the number less than 50?” “Yes.” “Is the number less than 25?” “No.” And so on, halving the interval at each step until only one number is left. This technique is known colloquially as the binary chop.

Your first task is to write a function that takes a target number and an array of numbers in non-decreasing order and returns either the position of the number in the array, or -1 to indicate the target number is not in the array. For instance, `bsearch(32, [13 19 24 29 32 37 43])` should return 4, since 32 is the fourth element of the array (counting from zero).

Beware that this exercise is harder than it looks. Jon Bentley, in his book Programming Pearls, reports that 90% of professional programmers cannot write a proper implementation of binary search in two hours, and Donald Knuth, in the second volume of his book The Art of Computer Programming, reports that though the first binary search was published in 1946, the first bug-free binary search wasn’t published until 1962.

Thus, your second task is to write a suitable test program that shows the accuracy of your binary search function.

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))&#93;
&#91;(> 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])
```