stupid_bs

import unittest

def bsearch_left(items, v):
    '''
    Binary search, finds left-most position.
    Returns (bool, insertion-point after which
    element should be inserted to maintain an invariant).
    '''
    if v is None:
        raise ValueError('v must be set')
    if not items:
        raise ValueError('items must be set')
    left = 0
    right = len(items) - 1
    
    while left < right:
        midpoint = (left + right) // 2
        if v <= items[midpoint]:
            right = midpoint
        else:
            left = midpoint + 1
            
    item = items[left]
    insertion_point = left if v >= item else left - 1 
    
    return v == item, insertion_point
    

class Test(unittest.TestCase):
    def test_single(self):
        self.assertEqual(bsearch_left([1], 1), (True, 0))
    
    def test_middle(self):
        items = [1,2,2,3]
        self.assertEqual(bsearch_left(items, 2), (True, 1))
    
    def test_left(self):
        items = [1,2,2,3]
        self.assertEqual(bsearch_left(items, 1), (True, 0))
    
    def test_right(self):
        items = [1,2,2,3]
        self.assertEqual(bsearch_left(items, 3), (True, 3))
        
    def test_missing_single(self):
        self.assertEqual(bsearch_left([1], 3), (False, 0))
    
    def test_missing_middle(self):
        items = [1,2,4,5]
        self.assertEqual(bsearch_left(items, 3), (False, 1))
    
    def test_missing_left(self):
        items = [1,2,2,3]
        self.assertEqual(bsearch_left(items, 0), (False, -1))
    
    def test_missing_right(self):
        items = [1,2,2,3]
        self.assertEqual(bsearch_left(items, 4), (False, 3))
        
        
if __name__ == '__main__':
    unittest.main()