검색의 수학: 선형 vs 이진

def linear_search(arr, target):
    for i, x in enumerate(arr):
        if x == target:
            return i
    return -1


arr = [3, 1, 4, 1, 5, 9, 2, 6, 5]
print(linear_search(arr, 5))  # 4
# 정렬 불필요 — 어떤 배열에도 동작
# 100만 개 → 평균 50만 비교

def binary_search(arr, target):
    """전제: arr가 정렬됨"""
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1


sorted_arr = sorted([3, 1, 4, 1, 5, 9, 2, 6, 5])
print(binary_search(sorted_arr, 5))  # 5나 6 위치


# 100만 개 → log₂(1,000,000) ≈ 20번 비교
# 100만 → 50만 → 25만 → 12.5만 → ... → 1 (20단계)

import time

n = 10_000_000
arr = list(range(n))
target = n - 1

t0 = time.perf_counter()
linear_search(arr, target)
t_linear = time.perf_counter() - t0

t0 = time.perf_counter()
binary_search(arr, target)
t_binary = time.perf_counter() - t0

print(f"선형 ({n:,}개): {t_linear*1000:.1f}ms")
print(f"이진 ({n:,}개): {t_binary*1000:.4f}ms")
print(f"속도 차이: {t_linear / t_binary:.0f}배")
# 약 100,000배 이상 빠름

import bisect

arr = [1, 3, 4, 4, 6, 7, 9]

# 위치 찾기 (값이 들어갈 곳)
print(bisect.bisect_left(arr, 4))   # 2 (왼쪽)
print(bisect.bisect_right(arr, 4))  # 4 (오른쪽)


# 정렬 유지하며 삽입
bisect.insort(arr, 5)
print(arr)  # [1, 3, 4, 4, 5, 6, 7, 9]


# 직접 검색
def binary_search_bisect(arr, target):
    i = bisect.bisect_left(arr, target)
    if i < len(arr) and arr[i] == target:
        return i
    return -1


print(binary_search_bisect(arr, 5))  # 4

def interpolation_search(arr, target):
    """균등 분포 데이터에서 이진 검색보다 빠름"""
    lo, hi = 0, len(arr) - 1

    while lo <= hi and arr[lo] <= target <= arr[hi]:
        if arr[hi] == arr[lo]:
            if arr[lo] == target: return lo
            return -1

        # 비례식으로 위치 추정
        pos = lo + ((target - arr[lo]) * (hi - lo)) // (arr[hi] - arr[lo])

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

    return -1


# 균등 분포 — 빠름
arr_uniform = list(range(0, 1_000_000, 10))
print(interpolation_search(arr_uniform, 500_000))  # 50000


# 비균등 분포 — 이진 검색보다 느릴 수 있음
arr_skewed = [1] * 999 + list(range(1, 1001))
# interpolation_search는 약함 → binary_search 추천

-- B-Tree 인덱스 = 다진 균형 트리
-- 100만 행 → 약 3~4단계 (각 노드가 100~1000 키)

-- 인덱스 없음
SELECT * FROM users WHERE email = 'alice@example.com';
-- O(n) 풀 스캔 — 100만 행 모두 비교

-- 인덱스 있음
CREATE INDEX idx_email ON users(email);
SELECT * FROM users WHERE email = 'alice@example.com';
-- O(log n) — 약 20번 비교


-- 단, INSERT/UPDATE는 인덱스 갱신 비용 발생
-- 읽기 위주 컬럼만 인덱싱

# 1. List — O(n)
nums = list(range(1_000_000))
999_999 in nums  # ~10ms

# 2. Set — O(1) 평균 (해시)
nums_set = set(nums)
999_999 in nums_set  # ~0.001ms

# 3. Dict — O(1) 평균 (해시)
nums_dict = {n: n for n in nums}
999_999 in nums_dict  # ~0.001ms

# 4. Sorted List + bisect — O(log n)
import bisect
i = bisect.bisect_left(nums, 999_999)
exists = i < len(nums) and nums[i] == 999_999  # ~0.0005ms

# 5. Tree (sortedcontainers) — O(log n)
from sortedcontainers import SortedList
sl = SortedList(nums)
999_999 in sl  # ~0.001ms