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

# Binary search for the target in a sorted array, assume the array has no dups
# 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
    assert binary_search(case1,0) == 0
    assert binary_search(case1, 0.5) == -1

def binary_search(l, target):
    left = 0
    right = len(l)-1
    while right >= left:
        m = (right - left )//2
        if l[m] == target:
            return m
        if target < l[m]:
            right = m - 1
        else:
            left = m + 1
    return -1