Binary Search

"""Topic  : Binary Search — Iterative & Recursive Implementation
Time   : O(log n)
Space  : O(1) iterative, O(log n) recursive stack"""

import random


#── Iterative Binary Search ────────────────────────────────────────────────────────────

def binary_search_iterative(
    arr: list[int], target: int
) -> int:
    """Binary search based on a loop.

    Returns:
        The found index, or -1 if not found"""
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1


#── Recursive Binary Search ────────────────────────────────────────────────────────────

def binary_search_recursive(
    arr: list[int], target: int, left: int, right: int
) -> int:
    """Recursive-based binary search.

    Returns:
        The found index, -1 if not found"""
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)


#── Step-by-Step Visualization ──────────────────────────────────────────────────────────

def binary_search_verbose(arr: list[int], target: int) -> int:
    """Proceed while printing the steps of binary search."""
    left, right = 0, len(arr) - 1
    step = 0
    print(f"Search Array: {arr}")
    print(f"Target Value: {target}")
    print("-" * 50)

    while left <= right:
        step += 1
        mid = (left + right) // 2
        #Array Visualization
        display = []
        for i, v in enumerate(arr):
            if i == mid:
                display.append(f"[{v}]")     #Pivot
            elif left <= i <= right:
                display.append(f" {v} ")
            else:
                display.append(f" · ")
        print(f"Step {step:2d}: {''.join(display)}")
        print(f"      left={left}, mid={mid}, right={right}, "
              f"arr[mid]={arr[mid]}")

        if arr[mid] == target:
            print(f"→ Found! Index {mid}")
            return mid
        elif arr[mid] < target:
            print(f"→ {arr[mid]} < {target}, searching right")
            left = mid + 1
        else:
            print(f"→ {arr[mid]} > {target}, searching left")
            right = mid - 1

    print(f"→ Not found (-1)")
    return -1


#── Main ────────────────────────────────────────────────────────────────────────

if __name__ == "__main__":
    arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

    print("=" * 55)
    print("Binary Search — Iterative vs Recursive")
    print("=" * 55)

    for target in [7, 1, 19, 6]:
        it = binary_search_iterative(arr, target)
        rec = binary_search_recursive(arr, target, 0, len(arr) - 1)
        status = "✓" if it == rec else "✗"
        print(f"target={target:3d}: Iterative={it:3d}, Recursive={rec:3d} {status}")

    #Step-by-Step Visualization
    binary_search_verbose(arr, 7)
    binary_search_verbose(arr, 6)

    #Comparison Count Analysis
    print("=== Comparison Count Analysis ===")
    n = len(arr)
    import math
    print(f"Array Length n={n}, Maximum Comparison Count ≈ log₂({n}) = {math.log2(n):.1f}")

    #Accuracy Verification
    test_arr = sorted(random.sample(range(1, 1000), 100))
    for t in random.sample(test_arr, 20) + [999, 0]:
        expected = test_arr.index(t) if t in test_arr else -1
        assert binary_search_iterative(test_arr, t) == expected
    print("Accuracy Verification: PASS")

"""Topic: bisect module — bisect_left, bisect_right, insort
Time: O(log n) search, O(n) insertion (insort)
Space: O(1)"""

from bisect import bisect_left, bisect_right, insort_left, insort_right


# ── bisect_left vs bisect_right ───────────────────────────────────────────────

def demo_bisect_basics() -> None:
    """The difference between bisect_left and bisect_right."""
    arr = [1, 3, 3, 3, 5, 7]
    print("=== bisect basics ===")
    print(f"Array: {arr}")
    print(f"Indices: {list(range(len(arr)))}")
    print()

    for target in [0, 1, 2, 3, 4, 5, 7, 8]:
        bl = bisect_left(arr, target)
        br = bisect_right(arr, target)
        print(f"  target={target}: bisect_left={bl}, bisect_right={br}")

    print()
    print("bisect_left(arr, x)  = First position greater than or equal to x (lower bound)")
    print("bisect_right(arr, x) = First position greater than x (upper bound)")


#── Check if value exists ─────────────────────────────────────────────────────────

def contains(arr: list[int], target: int) -> bool:
    """Check whether a value exists with bisect_left O(log n)."""
    idx = bisect_left(arr, target)
    return idx < len(arr) and arr[idx] == target


def demo_contains() -> None:
    """Check whether a value exists."""
    arr = sorted([5, 2, 8, 1, 9, 3, 7])
    print(f"\n=== Check if value exists ===")
    print(f"Array: {arr}")
    for target in [1, 4, 7, 10]:
        print(f"Does {target} exist? {contains(arr, target)}")


#── Count number of elements ────────────────────────────────────────────────────────────

def count_occurrences(arr: list[int], target: int) -> int:
    """Returns the number of target elements in a sorted array in O(log n)."""
    return bisect_right(arr, target) - bisect_left(arr, target)


def count_in_range(arr: list[int], lo: int, hi: int) -> int:
    """Returns the number of elements in a sorted array where lo ≤ x ≤ hi in O(log n)."""
    return bisect_right(arr, hi) - bisect_left(arr, lo)


def demo_count() -> None:
    """Counting the number of elements."""
    arr = [1, 2, 3, 3, 3, 4, 5, 5, 6]
    print(f"\n=== Count number of elements ===")
    print(f"Array: {arr}")
    for t in [1, 3, 5, 7]:
        cnt = count_occurrences(arr, t)
        print(f"Number of {t}: {cnt}")
    print(f"Count within range [2,5]: {count_in_range(arr, 2, 5)}")
    print(f"Count within range [3,3]: {count_in_range(arr, 3, 3)}")


#── insort: Insert while maintaining order ─────────────────────────────────────────────

def demo_insort() -> None:
    """Use insort_left / insort_right."""
    print(f"\n=== insort: Insert while maintaining order ===")
    arr: list[int] = []
    values = [5, 3, 8, 1, 3, 7]
    for v in values:
        insort_left(arr, v)
        print(f"  insort({v:2d}) → {arr}")

    print()
    arr2: list[int] = []
    for v in values:
        insort_right(arr2, v)
        print(f"  insort_right({v:2d}) → {arr2}")


#── Practical application: Number of people by grade range ─────────────────────────────

def demo_grade_count() -> None:
    """Calculate the number of people in each grade distribution interval."""
    scores = sorted([75, 82, 91, 65, 88, 73, 95, 78, 84, 60,
                     92, 71, 87, 68, 79])
    print(f"\n=== Number of people by grade range ===")
    print(f"Grade Distribution: {scores}")
    grades = [
        ("A (90~100)", 90, 100),
        ("B (80~89)",  80, 89),
        ("C (70~79)",  70, 79),
        ("D (60~69)",  60, 69),
    ]
    for label, lo, hi in grades:
        cnt = count_in_range(scores, lo, hi)
        print(f"{label}: {cnt} people")


#── Main ────────────────────────────────────────────────────────────────────────

if __name__ == "__main__":
    demo_bisect_basics()
    demo_contains()
    demo_count()
    demo_insort()
    demo_grade_count()

    #Accuracy Verification
    arr = sorted([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])
    assert count_occurrences(arr, 5) == arr.count(5)
    assert count_occurrences(arr, 1) == arr.count(1)
    assert count_in_range(arr, 3, 6) == sum(1 for x in arr if 3 <= x <= 6)
    print("\nAccuracy Verification: PASS")

"""Topic: Direct implementation and application of lower bound / upper bound
Time: O(log n)
Space: O(1)"""

from bisect import bisect_left, bisect_right


#── Direct Implementation of Lower Bound ─────────────────────────────────────────────

def lower_bound(arr: list[int], target: int) -> int:
    """Return the first index where the target is greater than or equal (same as bisect_left).

    The array must be sorted.
    If the return value is len(arr), then all elements < target"""
    left, right = 0, len(arr)
    while left < right:          #Note: left < right (right = len)
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left


def upper_bound(arr: list[int], target: int) -> int:
    """Return the first index exceeding the target (same as bisect_right).

    If the return value is len(arr), all elements are <= target"""
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left


#── Verification ─────────────────────────────────────────────────────────────────

def verify_bounds() -> None:
    """Direct implementation and comparison with the bisect module."""
    import random
    test_arrays = [
        [1, 3, 3, 3, 5, 7],
        [1],
        [],
        [1, 1, 1, 1],
        list(range(0, 20, 2)),   #Only even numbers
    ]
    print("=== Verification of lower/upper bound ===")
    for arr in test_arrays:
        targets = set(arr) | {0, -1, max(arr, default=0) + 1}
        for t in sorted(targets):
            lb = lower_bound(arr, t)
            ub = upper_bound(arr, t)
            assert lb == bisect_left(arr, t), f"lower_bound error: arr={arr}, t={t}"
            assert ub == bisect_right(arr, t), f"upper_bound error: arr={arr}, t={t}"
    print("All cases PASS")


#── Application: Number of Elements ────────────────────────────────────────────────

def count_equal(arr: list[int], target: int) -> int:
    """The number of elements in the sorted array that are the same as the target."""
    return upper_bound(arr, target) - lower_bound(arr, target)


def count_less_than(arr: list[int], target: int) -> int:
    """Number of elements less than the target."""
    return lower_bound(arr, target)


def count_greater_than(arr: list[int], target: int) -> int:
    """Number of elements exceeding the target."""
    return len(arr) - upper_bound(arr, target)


def count_range(arr: list[int], lo: int, hi: int) -> int:
    """The number of elements in the range lo ≤ x ≤ hi."""
    return upper_bound(arr, hi) - lower_bound(arr, lo)


#── Demo ────────────────────────────────────────────────────────────────────────

def demo_count_operations() -> None:
    """Element count operation demo."""
    arr = [1, 2, 3, 3, 3, 4, 4, 5, 6]
    print(f"=== Element Count Operations ===")
    print(f"Array: {arr}")
    print(f"Number of 3's               : {count_equal(arr, 3)}")
    print(f"Number of elements less than 3: {count_less_than(arr, 3)}")
    print(f"Number of elements greater than 3: {count_greater_than(arr, 3)}")
    print(f"Number of elements in range [2, 4]     : {count_range(arr, 2, 4)}")
    print(f"Number of elements in range [3, 5]     : {count_range(arr, 3, 5)}")


#── Application: Number Card Problem Style ────────────────────────────────────────

def solve_card_count(cards: list[int], queries: list[int]) -> list[int]:
    """Calculate how many times each query value appears in the cards array in O(m log n).

    Baekjoon 10816 style"""
    cards_sorted = sorted(cards)
    return [count_equal(cards_sorted, q) for q in queries]


def demo_card_count() -> None:
    """Counting the number of cards."""
    cards = [6, 3, 2, 10, 10, 10, -10, -10, 7, 3]
    queries = [10, 9, -10, 3, 100]
    results = solve_card_count(cards, queries)
    print(f"=== Counting Number Cards ===")
    print(f"Cards: {sorted(cards)}")
    for q, r in zip(queries, results):
        print(f"{q:>5} → {r} pcs")


#── Main ────────────────────────────────────────────────────────────────────────

if __name__ == "__main__":
    verify_bounds()
    demo_count_operations()
    demo_card_count()

    #Additional Verification
    arr = [1, 2, 3, 3, 3, 4, 5]
    assert count_equal(arr, 3) == 3
    assert count_less_than(arr, 3) == 2
    assert count_greater_than(arr, 3) == 2
    assert count_range(arr, 2, 4) == 5
    print("Additional accuracy check: PASS")

"""Topic  : Binary Search Applications — First/Last Occurrence, Rotated Array Search
Time   : O(log n)
Space  : O(1)"""

from bisect import bisect_left, bisect_right


#── First and Last Occurrence ───────────────────────────────────────────────

def find_first(arr: list[int], target: int) -> int:
    """First position of target in a sorted array.

    Return -1 if not found."""
    idx = bisect_left(arr, target)
    if idx < len(arr) and arr[idx] == target:
        return idx
    return -1


def find_last(arr: list[int], target: int) -> int:
    """The last position of target in a sorted array.

    Return -1 if not found."""
    idx = bisect_right(arr, target) - 1
    if idx >= 0 and arr[idx] == target:
        return idx
    return -1


def demo_first_last() -> None:
    """First/Last appearance location demo."""
    arr = [1, 2, 3, 3, 3, 3, 4, 5]
    print("=== First / Last Occurrence ===")
    print(f"Array: {arr}")
    for target in [1, 3, 5, 6]:
        first = find_first(arr, target)
        last = find_last(arr, target)
        print(f"target={target}: first={first:2d}, last={last:2d}")


#── Search in Rotated Sorted Array ──────────────────────────────────────────

def search_rotated(arr: list[int], target: int) -> int:
    """Search for target in a rotated sorted array.

    Example: [4, 5, 6, 7, 0, 1, 2] — rotated from the original [0,1,2,4,5,6,7]
    Time: O(log n)"""
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        #Left half is sorted
        if arr[left] <= arr[mid]:
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        #Right half is sorted
        else:
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1


def demo_rotated_search() -> None:
    """Rotated sorted array search demo."""
    rotated = [4, 5, 6, 7, 0, 1, 2]
    print(f"\n=== Search in Rotated Sorted Array ===")
    print(f"Array: {rotated}")
    for target in [0, 4, 7, 3]:
        idx = search_rotated(rotated, target)
        print(f"target={target}: index={idx}")


#── k-th Smallest Element (Two Sorted Arrays) ──────────────────────────────

def find_kth_in_sorted_arrays(
    a: list[int], b: list[int], k: int
) -> int:
    """The k-th element merged from two sorted arrays O(log(m+n)).

    Simple implementation: Determine the partition point using binary search"""
    #k is 1-indexed
    if len(a) > len(b):
        a, b = b, a     #a should be shorter
    lo = max(0, k - len(b))
    hi = min(k, len(a))

    while lo <= hi:
        i = (lo + hi) // 2
        j = k - i
        a_left = a[i - 1] if i > 0 else float('-inf')
        a_right = a[i] if i < len(a) else float('inf')
        b_left = b[j - 1] if j > 0 else float('-inf')
        b_right = b[j] if j < len(b) else float('inf')

        if a_left <= b_right and b_left <= a_right:
            return int(max(a_left, b_left))
        elif a_left > b_right:
            hi = i - 1
        else:
            lo = i + 1
    return -1


def demo_kth_sorted() -> None:
    """The k-th element in two sorted arrays."""
    a = [1, 3, 8, 9, 15]
    b = [7, 11, 18, 19, 21, 25]
    merged = sorted(a + b)
    print(f"\n=== k-th Element in Two Sorted Arrays ===")
    print(f"a = {a}")
    print(f"b = {b}")
    print(f"Merged sorted: {merged}")
    for k in [1, 3, 6, 11]:
        result = find_kth_in_sorted_arrays(a, b, k)
        expected = merged[k - 1]
        status = "✓" if result == expected else "✗"
        print(f"k={k:2d}: {result} (expected: {expected}) {status}")


#── Integer Square Root (Binary Search) ───────────────────────────────────

def integer_sqrt(n: int) -> int:
    """Calculate floor(sqrt(n)) using binary search.

    Python has math.isqrt, but this is practice for the concept of binary search."""
    if n < 0:
        raise ValueError("No square root for negative numbers")
    if n == 0:
        return 0
    left, right = 1, n
    while left <= right:
        mid = (left + right) // 2
        sq = mid * mid
        if sq == n:
            return mid
        elif sq < n:
            left = mid + 1
        else:
            right = mid - 1
    return right


def demo_sqrt() -> None:
    """Integer square root using binary search."""
    import math
    print(f"\n=== Integer Square Root (Binary Search) ===")
    for n in [0, 1, 4, 8, 9, 15, 16, 100, 1000000]:
        result = integer_sqrt(n)
        expected = math.isqrt(n)
        status = "✓" if result == expected else "✗"
        print(f"  sqrt({n:>8}) = {result:>5} {status}")


#── Main ────────────────────────────────────────────────────────────────────────

if __name__ == "__main__":
    demo_first_last()
    demo_rotated_search()
    demo_kth_sorted()
    demo_sqrt()

    #Accuracy Verification
    rotated_tests = [
        ([4, 5, 6, 7, 0, 1, 2], 0, 4),
        ([4, 5, 6, 7, 0, 1, 2], 3, -1),
        ([1], 0, -1),
        ([1], 1, 0),
    ]
    for arr, t, exp in rotated_tests:
        assert search_rotated(arr, t) == exp
    print("\nAccuracy Verification: PASS")