Skip to content

Instantly share code, notes, and snippets.

@shabda
Forked from akshar-raaj/binsearch
Created November 24, 2012 11:07
Show Gist options
  • Save shabda/4139208 to your computer and use it in GitHub Desktop.
Save shabda/4139208 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 = [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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment