Practice implementation of binary search.

binary_search.py

"""Practice implementation of binary search."""

import pytest
from typing import Sequence

def binary_search(sorted_arr: Sequence[int], target:int) -> int:
    """Find the index of target in sorted_arr.
    
    Returns:
        Index of the target or -1 if not found. Picks the first match randomly if there are multiple.
    """
    # alias for typing speed
    a = sorted_arr
    if not a or len(a) == 0:
        return -1

    left = 0
    right = len(a)
    #print('start')
    while left < right:
        ptr = (left + right) // 2
        #print('val', a[ptr], 'ptr', ptr, 'left', left, 'right', right)
        if a[ptr] == target:
            return ptr
        elif ptr in (left, right):
            break
        elif a[ptr] < target:
            left = ptr + 1
        elif a[ptr] > target:
            # Target is to the left
            right = ptr

        
    return -1

def test_big():
    assert binary_search(list(range(10)), 1) == 1
    assert binary_search(list(range(100)), 95) == 95

def test_edges():
    assert binary_search(list(range(10)), 0) == 0
    assert binary_search(list(range(100)), 99) == 99
    assert binary_search(list(range(100)), 100) == -1
    assert binary_search(list(range(100)), -1) == -1

    
def test_empty():
    assert binary_search([], 5) == -1
    assert binary_search(None, 5) == -1

def test_unit():
    assert binary_search([1], 5) == -1
    assert binary_search([1], 1) == 0
    

    
if __name__ == '__main__':
    #pytest.main(['-k big', '-s'])
    pytest.main()