binary_search.py

import random
import unittest

def _binary_search_from_pivot(lst, el, pivot_point):
    # returnss.......
    # - another range to searach
    # - the answer
    pass

def binary_search(lst, el):
    if len(lst) == 0:
        return None

    assert len(lst) > 0

    low = 0
    high = len(lst)-1
    while high != low:
        mid = (low+high)//2
        if lst[mid] == el:
            return mid
        elif lst[mid] < el:
            low = mid+1
        else:
            high = mid-1

    if lst[low] == el:
        return low
    else:
        return None

class TestBinarySearch(unittest.TestCase):

    def test_random(self):
        for i in range(1, 50):
            lst = list(range(0, 100000, i+1))
            el = random.randint(0, 100000)
            result = binary_search(lst, el)
            if result is not None:
                self.assertEqual(lst[result], el)
    
    def test_missing(self):
        self.assertEqual(binary_search([1,2,3,4,6], 5), None)

    def test_empty(self):
        self.assertEqual(binary_search([], 5), None)

    def test_first(self):
        self.assertEqual(binary_search([1,2], 1), 0)
    
    def test_last(self):
        self.assertEqual(binary_search([1,2], 2), 1)


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