Leftmost binary search stress test

leftmost-binary-search-stress-test.py

import random

def leftmost_bsearch(L, T):
    l, r = 0, len(L)

    while l < r:
        for smol in L[0:l]:
            assert smol < T
        for somewhat_lorg in L[r:len(L)]:
            assert somewhat_lorg >= T  # weak inequality

        mid = (l + r) // 2

        if L[mid] < T:
            l = mid + 1
        else:
            r = mid

    return l  # return the first element AFTER L[0:l]

def test_leftmost_bsearch(trials=10000):
    for _ in range(trials):
        # Generate a random sorted list
        size = random.randint(0, 100)  # List of size 0 to 100
        L = sorted(random.randint(-1000, 1000) for _ in range(size))
        
        # Choose a random target
        T = random.randint(-1000, 1000)
        
        # Compute expected result using built-in Python search
        expected = 0
        while expected < len(L) and L[expected] < T:
            expected += 1
        
        # Get result from our function
        result = leftmost_bsearch(L, T)
        
        # Validate correctness
        assert result == expected, f"Failed on L={L}, T={T}: got {result}, expected {expected}"
    
    print("All tests passed!")

# Run the test
if __name__ == "__main__":
    test_leftmost_bsearch()