Binary search stress test

binary-search-stress-test.py

import random

def bsearch(L, T):
    l, r = 0, len(L)
    
    while l < r:
        for smol in L[0:l]:
            assert smol < T
        for lorg in L[r:len(L)]:
            assert lorg > T
        
        mid = (l + r) // 2
        if L[mid] == T:
            return mid
        elif L[mid] < T:
            l = mid + 1
        else:
            r = mid
    
    return -1

def generate_test_case(include_target, allow_duplicates):
    size = random.randint(10, 50)  # Random list size between 10 and 50
    numbers = [random.randint(10, 99) for _ in range(size)]
    
    if not allow_duplicates:
        numbers = list(set(numbers))  # Remove duplicates if not allowed
    
    numbers.sort()  # Ensure the list is sorted
    
    if include_target:
        T = random.choice(numbers)  # Pick an existing number as target
    else:
        while True:
            T = random.randint(10, 99)
            if T not in numbers:
                break  # Ensure T is not in the list
    
    return numbers, T

def run_tests():
    num_tests = 10000
    categories = [
        (True, False),  # No duplicates, contains T
        (True, True),   # Duplicates, contains T
        (False, False), # No duplicates, does not contain T
        (False, True)   # Duplicates, does not contain T
    ]
    
    results = {category: 0 for category in categories}
    
    for _ in range(num_tests):
        category = random.choice(categories)  # Randomly select a category for each test
        include_target, allow_duplicates = category
        L, T = generate_test_case(include_target, allow_duplicates)
        result = bsearch(L, T)
        
        correct = (result != -1 and L[result] == T) or (result == -1 and T not in L)
        status = "✔" if correct else "✘"
        
        print(f"Array: {L}\nTarget: {T}\nReturned Index: {result}\nResult: {status}\n")
        
        results[category] += 1
    
    print("All tests completed.")
    for category, count in results.items():
        print(f"{category}: {count} tests run.")

run_tests()