Skip to content

Instantly share code, notes, and snippets.

@akshar-raaj
Created November 24, 2012 10:32
Show Gist options
  • Save akshar-raaj/4139128 to your computer and use it in GitHub Desktop.
Save akshar-raaj/4139128 to your computer and use it in GitHub Desktop.
Binary Search
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()
@akshar-raaj
Copy link
Author

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]

@shabda
Copy link

shabda commented Nov 24, 2012

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment