Binary Search ใน Python อธิบายพร้อมตัวอย่าง

Binary Search คืออะไร?

Binary Search เป็น Searching Algorithm สำหรับค้นหา Element ใน Sorted Array เท่านั้น ไม่สามารถใช้กับ Unsorted Array ได้

Time Complexity: O(log n) (ดีกว่า Linear Search O(n) มาก)

Binary Search ทำงานอย่างไร?

1. เปรียบเทียบ Target กับ Middle Element ของ Array
2. ถ้าเท่ากัน → เจอแล้ว Return Index
3. ถ้า Target < Middle → ค้นหาใน Half ซ้าย (Left Half)
4. ถ้า Target > Middle → ค้นหาใน Half ขวา (Right Half)
5. ทำซ้ำจนกว่าจะเจอ หรือ Left > Right (ไม่เจอ)

ตัวอย่างการทำงาน (Visual)

Sorted Array: [2, 5, 6, 8, 10, 11, 13, 15, 16] (Indices 0-8)
Target: 6

Round 1

L=0, H=8, Mid=4 → arr[4]=10

6 < 10 → ไป Half ซ้าย: H = Mid-1 = 3

Round 2

L=0, H=3, Mid=1 → arr[1]=5

6 > 5 → ไป Half ขวา: L = Mid+1 = 2

Round 3

L=2, H=3, Mid=2 → arr[2]=6

6 == 6 → เจอที่ Index 2!

Implementation (Iterative)

def binary_search(arr, x):
    l = 0
    r = len(arr) - 1
    
    while l <= r:
        mid = (l + r) // 2
        
        if arr[mid] == x:
            return mid          # เจอ
        elif x < arr[mid]:
            r = mid - 1         # ค้นหา Half ซ้าย
        else:
            l = mid + 1         # ค้นหา Half ขวา
    
    return -1  # ไม่เจอ

# ทดสอบ
array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(binary_search(array, 7))   # 6 (Index 6)
print(binary_search(array, 15))  # -1 (Not found)

ผลลัพธ์

6
-1

Implementation (Recursive)

def binary_search_recursive(arr, x, l=0, r=None):
    if r is None:
        r = len(arr) - 1
    
    if l > r:
        return -1
    
    mid = (l + r) // 2
    
    if arr[mid] == x:
        return mid
    elif x < arr[mid]:
        return binary_search_recursive(arr, x, l, mid - 1)
    else:
        return binary_search_recursive(arr, x, mid + 1, r)

Built-in: bisect Module

import bisect

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

# bisect_left: หา Index ที่ควร Insert เพื่อรักษา Order (ซ้ายสุด)
idx = bisect.bisect_left(arr, 7)
print(idx)  # 6

# ตรวจสอบว่ามีจริง
if idx < len(arr) and arr[idx] == 7:
    print("Found at", idx)
else:
    print("Not found")

# bisect_right: ขวาสุด
print(bisect.bisect_right(arr, 7))  # 7

Complexity Comparison

ข้อจำกัด

• ต้องเรียงข้อมูลก่อน (O(n log n))
• ไม่เหมาะกับ Linked List (Random Access ช้า)
• สำหรับข้อมูลเล็ก Linear Search เร็วกว่า (Overhead น้อยกว่า)