Binary Search & Variations

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid           # เจอ คืน index
        elif arr[mid] < target:
            lo = mid + 1         # ตัดครึ่งซ้ายทิ้ง
        else:
            hi = mid - 1         # ตัดครึ่งขวาทิ้ง
    return -1                    # ไม่เจอ

print(binary_search([1, 3, 5, 7, 9], 7))   # 3

import bisect

arr = [1, 3, 5, 7, 9]
print(bisect.bisect_left(arr, 5))    # 2  (ตำแหน่งของ 5)
print(bisect.bisect_right(arr, 5))   # 3  (หลัง 5)
print(bisect.bisect_left(arr, 6))    # 3  (ตำแหน่งที่ควรแทรก 6)

bisect.insort(arr, 6)    # แทรกแบบคงการเรียง
print(arr)               # [1, 3, 5, 6, 7, 9]

import bisect
nums = [1, 2, 2, 2, 3]
# จำนวน 2 ทั้งหมด = ขอบขวา - ขอบซ้าย
left = bisect.bisect_left(nums, 2)    # 1
right = bisect.bisect_right(nums, 2)  # 4
print(right - left)                   # 3  (มี 2 อยู่ 3 ตัว)