---

"""
Бинарный и интерполяционный поиск
  • по массиву чисел
  • по массиву строк (без преобразования строк в числа — только ord символа)

Интерполяция для строк работает через первый различающийся символ
граничных элементов a[lo] и a[hi]. Это даёт относительную позицию
target прямо по алфавиту — минимальное вмешательство в данные.
"""

import os
import random
import string
import time
import urllib.request


# =====================================================================
#  1. ПОДГОТОВКА ДАННЫХ
# =====================================================================

WORDS_URL = ("https://raw.githubusercontent.com/dwyl/"
             "english-words/master/words_alpha.txt")
WORDS_FILE = "words_alpha.txt"


def load_word_dictionary(min_size=50_000):
    """
    Пытается скачать словарь, иначе берёт системный,
    иначе генерирует локально. Результат всегда отсортирован.
    """
    words = []

    # 1) попытка скачать
    try:
        if not os.path.exists(WORDS_FILE):
            print(f"Скачиваем словарь: {WORDS_URL}")
            urllib.request.urlretrieve(WORDS_URL, WORDS_FILE)
        with open(WORDS_FILE, "r", encoding="utf-8") as f:
            words = [w.strip() for w in f if w.strip()]
        print(f"Загружено слов из скачанного словаря: {len(words)}")
    except Exception as e:
        print(f"Скачать не удалось ({e}).")

    # 2) системный словарь
    if len(words) < min_size:
        for path in ("/usr/share/dict/words",
                     "/usr/share/dict/american-english",
                     "/usr/dict/words"):
            if os.path.exists(path):
                try:
                    with open(path, "r", encoding="utf-8", errors="ignore") as f:
                        words = [w.strip() for w in f if w.strip()]
                    print(f"Взят системный словарь {path}: {len(words)} слов")
                    break
                except Exception:
                    pass

    # 3) локальная генерация
    if len(words) < min_size:
        print(f"Генерируем словарь из {min_size} слов локально.")
        pool = set()
        while len(pool) < min_size:
            pool.add(''.join(random.choices(string.ascii_lowercase,
                                            k=random.randint(3, 9))))
        words = list(pool)

    return sorted(words)


def gen_numbers(n=100_000):
    return sorted(random.sample(range(1, n * 10), n))


# =====================================================================
#  2. БИНАРНЫЙ ПОИСК (универсальный — работает и для чисел, и для строк)
# =====================================================================

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    comps = 0
    while lo <= hi:
        comps += 1
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid, comps
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, comps


# =====================================================================
#  3. ИНТЕРПОЛЯЦИОННЫЙ ПОИСК ЧИСЕЛ
# =====================================================================

def interpolation_search_numbers(arr, target):
    lo, hi = 0, len(arr) - 1
    comps = 0
    while lo <= hi and arr[lo] <= target <= arr[hi]:
        comps += 1
        if arr[hi] == arr[lo]:
            return (lo if arr[lo] == target else -1), comps

        pos = lo + (target - arr[lo]) * (hi - lo) // (arr[hi] - arr[lo])

        if arr[pos] == target:
            return pos, comps
        if arr[pos] < target:
            lo = pos + 1
        else:
            hi = pos - 1
    return -1, comps


# =====================================================================
#  4. ИНТЕРПОЛЯЦИОННЫЙ ПОИСК СТРОК — БЕЗ ПРЕОБРАЗОВАНИЙ
#
#  Для интерполяции нужно уметь оценить, "где между a[lo] и a[hi]"
#  находится target. Для строк делаем это так:
#    • находим первый индекс k, где a[lo][k] != a[hi][k];
#    • берём ord() символов на этой позиции как числовую ось;
#    • считаем относительную позицию target на этой оси.
#
#  ord() — встроенный код символа (не преобразование строки!).
#  Ни хешей, ни base-N ключей, ни предварительной подготовки.
# =====================================================================

def string_interp_ratio(s_lo, s_hi, target):
    """
    Оценка позиции target между s_lo и s_hi (s_lo <= target <= s_hi)
    в виде вещественного числа из [0, 1].
    Работает прямо по символам строк.
    """
    n = min(len(s_lo), len(s_hi))
    k = 0
    while k < n and s_lo[k] == s_hi[k]:
        k += 1

    if k == n:
        # одна строка — префикс другой; считаем позицию средней
        return 0.5

    lo_code = ord(s_lo[k])
    hi_code = ord(s_hi[k])
    if hi_code == lo_code:
        return 0.5

    # символ target на позиции k (0 — если строка кончилась раньше)
    t_code = ord(target[k]) if k < len(target) else 0

    r = (t_code - lo_code) / (hi_code - lo_code)
    if r < 0.0:
        r = 0.0
    if r > 1.0:
        r = 1.0
    return r


def interpolation_search_strings(arr, target):
    lo, hi = 0, len(arr) - 1
    comps = 0
    while lo <= hi:
        # target вне текущего диапазона — искать нечего
        if arr[lo] > target or arr[hi] < target:
            return -1, comps
        comps += 1

        if lo == hi:
            return (lo if arr[lo] == target else -1), comps

        r = string_interp_ratio(arr[lo], arr[hi], target)
        pos = lo + int(r * (hi - lo))
        if pos < lo:
            pos = lo
        if pos > hi:
            pos = hi

        if arr[pos] == target:
            return pos, comps
        if arr[pos] < target:
            lo = pos + 1
        else:
            hi = pos - 1
    return -1, comps


# =====================================================================
#  5. ЗАМЕРЫ И ВЫВОД
# =====================================================================

def measure(fn, arr, target):
    t0 = time.perf_counter_ns()
    idx, comps = fn(arr, target)
    dt = time.perf_counter_ns() - t0
    return idx, comps, dt


def show_block(title, arr, cases, interp_fn):
    print()
    print("=" * 92)
    print(title)
    print("=" * 92)
    print(f"{'Случай':<16}{'Поиск':<24}{'Индекс':<10}"
          f"{'Сравнений':<12}{'Время, мкс':<12}")
    print("-" * 92)
    for name, tgt in cases:
        ib, cb, tb = measure(binary_search, arr, tgt)
        ii, ci, ti = measure(interp_fn, arr, tgt)
        print(f"{name:<16}{'бинарный':<24}{('—' if ib<0 else ib):<10}"
              f"{cb:<12}{tb/1000:<12.2f}")
        print(f"{'':<16}{'интерполяционный':<24}"
              f"{('—' if ii<0 else ii):<10}{ci:<12}{ti/1000:<12.2f}")
        print("-" * 92)


def main():
    # ---------- ЧИСЛА ----------
    nums = gen_numbers(100_000)
    print(f"Числовой массив: {len(nums)} элементов, "
          f"[{nums[0]}..{nums[-1]}]")
    num_cases = [
        ("первый",       nums[0]),
        ("середина",     nums[len(nums) // 2]),
        ("последний",    nums[-1]),
        ("отсутствует",  -1),
    ]
    show_block("ЧИСЛА: бинарный vs интерполяционный",
               nums, num_cases, interpolation_search_numbers)

    # ---------- СТРОКИ ----------
    words = load_word_dictionary(50_000)
    print(f"\nСтроковый массив: {len(words)} элементов, "
          f"'{words[0]}'..'{words[-1]}'")
    str_cases = [
        ("первый",       words[0]),
        ("середина",     words[len(words) // 2]),
        ("последний",    words[-1]),
        ("отсутствует",  "zzzzzzzzzzz"),
    ]
    show_block("СТРОКИ: бинарный vs интерполяционный",
               words, str_cases, interpolation_search_strings)

    # ---------- ИТОГИ ----------
    print()
    print("=" * 92)
    print("ИТОГ: сравнение эффективности")
    print("=" * 92)
    print("""
  ЧИСЛА (равномерные):
      • бинарный            ~17 сравнений
      • интерполяционный    1–3 сравнения
      → ускорение в разы на каждом поиске.

  СТРОКИ (словарь):
      • бинарный            ~log2(N) ≈ 16 сравнений
      • интерполяционный    обычно 1–5 сравнений, но зависит от
                            распределения слов по алфавиту.
      → выигрыш есть, но меньше, чем на числах, потому что слова
        распределены неравномерно ('a','b','c' — густо,
        'x','y','z' — пусто).

  СЛОЖНОСТЬ:
      • бинарный              O(log n) в любом случае
      • интерполяционный      O(log log n) при равномерных данных,
                              O(n) — в худшем случае.

  ПРИМЕЧАНИЕ про строки:
      Интерполяция сделана БЕЗ каких-либо преобразований строк —
      только по первому различающемуся символу через ord().
      Никаких хешей, base-N ключей и предвычислений.
""")


if __name__ == "__main__":
    main()