Binary Search

binsearch

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 = [0, 0, 0, 0]
       self.assertEquals(binsearch(lst, 0,), 0)"""

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

    def test_randoms(self):
       import random
       size = random.randint(0, 10)
       lst = sorted([random.randint(0, 10) for i in range(size)])
       lst = list(set(lst)) #we are already aware of bug in case there are duplicates
       if lst: #lst can be an empty list and then lst[0] will be an error
           self.assertEquals(binsearch(lst, lst[0],), 0)


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

lst = list(set(lst))

This would mean tge list is not sorted any more.

If lst is sorted, won't set(lst) remain sorted and just duplicates removed?

In [1]: ls=[1,1,2,3,4]

In [2]: set(ls)
Out[2]: set([1, 2, 3, 4])

In [3]: ls = [1,1,1,2,2,3,3,5,7,7]

In [4]: set(ls)
Out[4]: set([1, 2, 3, 5, 7])

In [5]: list(set(ls))
Out[5]: [1, 2, 3, 5, 7]

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