ข้อ 53 · LC374 Guess Number Higher or Lower (ทายเลขสูงต่ำ) 🟢

โจทย์ (LC374): กำลังเล่นเกม Guess Game ที่มีการสุ่มเลขจำนวนเต็มหนึ่งตัวไว้ล่วงหน้าในช่วง 1 ถึง n ทุกครั้งที่เดา (guess) ผิด เกมจะบอกว่าตัวเลขที่สุ่มไว้มากกว่าหรือน้อยกว่าตัวที่เดา ให้เรียกใช้ API ที่มีให้อยู่แล้วคือ int guess(int num) ซึ่ง return -1 ถ้า num ที่เดามากกว่าตัวเลขที่สุ่มไว้ (เดาสูงไป), return 1 ถ้า num น้อยกว่า (เดาต่ำไป), และ return 0 ถ้าเดาถูก ให้ return ตัวเลขที่ระบบสุ่มไว้

แนวทาง — ต้องใช้อะไร & คิดยังไง

โครงสร้างที่ใช้: binary search พื้นฐานตรง ๆ answer space (ช่วงคำตอบ) sorted อยู่แล้ว (1 ถึง n) และ guess() ทำหน้าที่เหมือนการ compare nums[mid] กับ target แค่มันบอก direction (ทิศทาง) ให้เราแทน

คิดแบบง่าย/ช้าก่อน: ถ้า guess ไล่จาก 1, 2, 3, ... จะเป็น O(n) ซึ่งช้ามากเมื่อ n ใหญ่ แต่เพราะ guess บอก direction ได้ เรา halve (ตัดครึ่ง) ช่วงที่เป็นไปได้ทุกครั้ง เหลือ O(log n)

1. initialize lo = 1, hi = n
2. ระหว่าง lo <= hi: compute mid แล้วเรียก res = guess(mid)
3. ถ้า res == 0 ทายถูก return mid
4. ถ้า res < 0 (mid มากไป) เลขจริงอยู่ครึ่งซ้าย ตั้ง hi = mid - 1; ถ้า res > 0 (mid น้อยไป) ตั้ง lo = mid + 1

ไล่ทีละสเต็ป

จำลอง n = 10, เลขจริง = 6:

# LeetCode ให้ API guess() มาให้แล้ว ที่จำลองไว้ตรงนี้เพื่อให้บล็อกนี้รันได้เองทั้งก้อน
SECRET = 6

def guess(num):
    if num > SECRET:
        return -1          # ทายมากไป
    if num < SECRET:
        return 1           # ทายน้อยไป
    return 0               # ทายถูก


# กำหนดให้มี API guess(num) อยู่แล้ว:
#   guess(num) -> -1 ถ้า num มากไป, 1 ถ้า num น้อยไป, 0 ถ้าถูก

def guessNumber(n):
    lo, hi = 1, n
    while lo <= hi:
        mid = (lo + hi) // 2
        res = guess(mid)
        if res == 0:
            return mid          # ทายถูก
        elif res < 0:
            hi = mid - 1        # mid มากไป เลขจริงอยู่ครึ่งซ้าย
        else:
            lo = mid + 1        # mid น้อยไป เลขจริงอยู่ครึ่งขวา
    return -1  # ไม่ควรมาถึงตรงนี้

print(guessNumber(10))     # เลขลับคือ 6

6