binary_search.py

# Fiddly.

def binary_search(haystack, needle, lo=0, hi=None, size=None):
    if hi is None:
        hi = len(haystack) - 1
    if size is None:
        size = len(haystack)
    if size == 0:
        return -1
    t = ((hi - lo) / 2)
    current = haystack[lo + t]
    if current == needle:
        return lo + t
    elif lo == hi:
        return -1
    elif needle > current:
        return binary_search(
            haystack, needle, lo=lo+t+1, hi=hi, size=size
        )
    elif needle < current:
        return binary_search(
            haystack, needle, lo=lo, hi=t, size=size
        )

import unittest

class Tests(unittest.TestCase):
    
    def testOneItem(self):
        self.assertEqual(binary_search([3], 3), 0)
    
    def testOneItemNotFound(self):
        self.assertEqual(binary_search([3], 1), -1)
    
    def testTwoItemsFirstMatches(self):
        self.assertEqual(binary_search([1, 3], 1), 0)
    
    def testTwoItemsSecondMatches(self):
        self.assertEqual(binary_search([1, 3], 3), 1)
    
    def testThreeItemsNoMatch(self):
        self.assertEqual(binary_search([1, 3, 18], 4), -1)
    
    def testThreeItemsFirstMatches(self):
        self.assertEqual(binary_search([1, 3, 18], 1), 0)
    
    def testThreeItemsSecondMatches(self):
        self.assertEqual(binary_search([1, 3, 18], 3), 1)
    
    def testThreeItemsThirdMatches(self):
        self.assertEqual(binary_search([1, 3, 18], 18), 2)
    
    def testThreeItemsMultipleMaches(self):
        self.assertNotEqual(binary_search([3, 3, 3], 3), -1)
    
    def testZeroLengthArray(self):
        self.assertEqual(binary_search([], 1), -1)

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

binary_search([1, 2, 4, 5], 3) infinite recursion