interview-questions/search-and-sort/binary_search.py

# Time complexity: O(logn)
# Space complexity: O(1)

import pytest

def test_binary_search():
    case1 = [0,1,2,3]
    assert binary_search(case1,1) == 1

def binary_search(l, target):
    left = 0
    right = len(l)-1

    while right > left:
        m = (right - left )//2
        print(m)
        if l[m] == target:
            return m
        elif target < l[m]:
            right = m - 1
        else:
            left = m + 1
    return 0