หาตัวเลขที่หายไปในอาร์เรย์เรียงลำดับติดต่อกันใน Python

โจทย์: อาร์เรย์ A ขนาด n มีตัวเลข unique เรียงน้อยไปมาก แต่ขาด 1 ตัว หาตัวที่หายไป (O(log n) ด้วย Binary Search)

ตัวอย่าง: [1,2,3,4,5,6,7,9] → หายไปคือ 8

อัลกอริทึม Binary Search

สังเกต: ในอาร์เรย์สมบูรณ์ A[i] - i = A[0] (คงที่) หากขาดตัวหนึ่ง ความต่างจะเปลี่ยนหลังจุดที่ขาด

1. left=0, right=n-1
2. mid = (left+right)//2
3. ถ้า A[mid] - mid == A[0] → ด้านซ้ายสมบูรณ์ ตรวจสอบ mid+1 ถ้าขาด → คืน A[mid]+1 มิฉะนั้น left=mid+1
4. ถ้า A[mid] - mid != A[0] → ด้านซ้ายขาด ตรวจสอบ mid-1 ถ้าขาด → คืน A[mid]-1 มิฉะนั้น right=mid-1

ตัวอย่างโค้ด

def search_missing_item(A):
    n = len(A)
    left, right = 0, n - 1
    while right > left:
        mid = left + (right - left) // 2
        if A[mid] - mid == A[0]:
            if A[mid + 1] - A[mid] > 1:
                return A[mid] + 1
            else:
                left = mid + 1
        else:
            if A[mid] - A[mid - 1] > 1:
                return A[mid] - 1
            else:
                right = mid - 1
    return -1

A = [1, 2, 3, 4, 5, 6, 7, 9]
print(search_missing_item(A))  # 8

ผลลัพธ์

8

สรุป: Binary Search แบบปรับเปลี่ยน เปรียบเทียบ A[mid] - mid กับ A[0] เพื่อตัดสินใจไปซ้ายหรือขวา O(log n) time O(1) space