Binary Search

binsearch.py

not_found = -1
import unittest
class TestBinS(unittest.TestCase):
    def test_empty(self):
        lst = []
        key = 0
        self.assertEquals(binsearch(lst, 0,), -1)

    def test_equal(self):
       lst = [10, 10, 10, 10]
       self.assertEquals(lst[binsearch(lst, 10,)], 10)

    def test_negs(self):
       lst = [-10, -1, 0, 1 , 10]
       self.assertEquals(binsearch(lst, 0,), 2)

    def test_randoms(self):
      for i in range(100):
        import random
        import sys
        size = random.randint(1, sys.maxint)
        lst = sorted(set([random.randint(0, sys.maxint) for i in range(size)]))
        if not(binsearch(lst, lst[0],) == 0):
          print lst
        self.assertEquals(binsearch(lst, lst[0],), 0)

    def test_strings(self):
        lst = sorted(["ajay", "manoj", "vijay", "manoj"])
        self.assertEquals(lst[binsearch(lst, "ajay",)], "ajay")



def binsearch(slist, value, left=0, right=None):
    if not right:
        right = len(slist)-1
    return binarysearch(slist, value, left, right)

def binarysearch(slist, value, left, right):
    while(left<=right):
        mid = (left+right)/2
        if slist[mid]==value:
            return mid
        elif value<slist[mid]:
            right = mid-1
            return binarysearch(slist, value, left, right)
        else:
            left = mid+1
            return binarysearch(slist, value, left, right)
    return -1

if __name__=="__main__":
    unittest.main()