binary_pytest.py

from math import log2

import pytest

from binary_search import binary_search


class CounterElNumber:
    _lt_global_counter = 0
    _eq_global_counter = 0

    @classmethod
    def reset_counters(cls):
        cls._lt_global_counter = 0
        cls._eq_global_counter = 0

    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        self.__class__._lt_global_counter += 1
        return self.value < other.value

    def __eq__(self, other):
        self.__class__._eq_global_counter += 1
        return self.value == other.value


def test_simple():
    assert binary_search([1], 1) == 0
    assert binary_search([1, 2], 1) == 0
    assert binary_search([1, 2], 2) == 1
    assert binary_search([1, 2, 2], 2) == 1
    assert binary_search([1, 1, 1, 2, 2], 1) == 0
    with pytest.raises(LookupError):
        binary_search([1, 2], 3)


def test_loop_rnd_range(make_rnd_gen):
    for i in range(50):
        start, stop = make_rnd_gen(i, 0), make_rnd_gen(i, 1)
        start, stop = (start, stop) if start < stop else (stop, start)
        for expected_index, value in zip(range(stop - start), range(start, stop)):
            assert binary_search(list(range(start, stop)), value) == expected_index


def test_loop_rnd_gauss(make_rnd_gen):
    for i in range(1000):
        n_size = make_rnd_gen(i, 2)
        sorted_array = sorted([make_rnd_gen(i, 3) for _ in range(n_size)])
        last_value = sorted_array[-1]
        index = binary_search(sorted_array, last_value)
        expected_index = sorted_array.index(last_value)
        assert index == expected_index


def test_complexity(make_rnd_gen):
    """Test O(log n) complexity. Use number of comparison"""

    binary_lts = []
    linear_eqs = []
    for i in range(1000):
        i = make_rnd_gen(i, 4)
        binary_search([CounterElNumber(i) for i in range(10000)], CounterElNumber(i))
        binary_lts.append(CounterElNumber._lt_global_counter)
        CounterElNumber.reset_counters()
        [CounterElNumber(i) for i in range(10000)].index(CounterElNumber(i))
        linear_eqs.append(CounterElNumber._eq_global_counter)
        CounterElNumber.reset_counters()
    assert sum(linear_eqs) > sum(binary_lts)
    assert 1.3 * log2(sum(linear_eqs) / 1000) > sum(binary_lts) / 1000