LeetCode #153 หาเลขน้อยสุดใน rotated array: อ่านรอยต่อด้วย binary search

LeetCode #153 ให้ array จำนวนเต็มที่เดิมเรียงเพิ่มแบบไม่ซ้ำ แล้วถูกหมุน 0 ถึง n-1 ตำแหน่ง เราต้องหาค่าน้อยสุดในเวลาเป้าหมาย O(log n) เช่น [4,5,6,7,0,1,2] ตอบ 0

WHY ก่อน HOW: ข้อมูลยังประกอบด้วยช่วงเรียงสองช่วง เพียงเอาหางมาต่อหน้าหรือกลับกัน จุดต่ำสุดจึงเป็น “รอยต่อ” เพียงแห่งเดียว เหมือนชั้นหนังสือเรียงหมายเลขแล้วหมุนวงกลม เราไม่ต้องเปิดทุกเล่มถ้าใช้เลขปลายขวาบอกว่ากำลังอยู่ฝั่งไหน

วิธี 1: เดินหาค่าน้อยสุด

อ่านทุกสมาชิกแล้วเก็บ minimum ใช้เวลา O(n) พื้นที่ O(1) อ่านง่ายที่สุดและทำกับ iterable/stream ได้โดยไม่ต้อง random access วิธีนี้ยังเป็น oracle ดีมากสำหรับ test แต่ไม่ผ่านเป้าหมาย O(log n) ของโจทย์

วิธี 2: เรียงสำเนาแล้วหยิบตัวแรก

sorted(nums)[0] ใช้เวลา O(n log n) และพื้นที่ O(n) อ่านสั้นแต่ทิ้งโครงสร้าง “เดิมเรียงแล้วหมุน” ไปทั้งหมด ถ้าใช้ nums.sort() จะเปลี่ยน input ซึ่งไม่จำเป็น จึงเหมาะแค่ baseline สำหรับข้อมูลจิ๋ว ไม่ใช่วิธีสัมภาษณ์ที่ดี

วิธี 3: Binary search เทียบกับปลายขวา

ตั้ง left=0, right=n-1 แล้วดู mid ถ้า nums[mid] > nums[right] จุดต่ำสุดต้องอยู่ขวาของ mid; ไม่เช่นนั้น mid อาจเป็นคำตอบ จึงเก็บมันไว้ด้วย right=mid เมื่อสองขอบมาชนกัน เราพบรอยต่อ ใช้เวลา O(log n) พื้นที่ O(1) และไม่แก้ input นี่คือ best default ภายใต้ constraints ที่สมาชิกไม่ซ้ำ

from __future__ import annotations

import unittest


def find_min_linear(nums: list[int]) -> int:
    return min(nums)


def find_min_sort_copy(nums: list[int]) -> int:
    return sorted(nums)[0]


def find_min_binary(nums: list[int]) -> int:
    left, right = 0, len(nums) - 1
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    return nums[left]


class FindMinimumTests(unittest.TestCase):
    def test_examples_and_edges(self):
        cases = [
            ([3, 4, 5, 1, 2], 1),
            ([4, 5, 6, 7, 0, 1, 2], 0),
            ([11, 13, 15, 17], 11),
            ([9], 9),
            ([-1, 0, 1, -3, -2], -3),
        ]
        for solve in (find_min_linear, find_min_sort_copy, find_min_binary):
            for values, expected in cases:
                original = values.copy()
                with self.subTest(method=solve.__name__, values=values):
                    self.assertEqual(solve(values), expected)
                    self.assertEqual(values, original)

    def test_every_rotation_against_linear_oracle(self):
        base = [-9, -2, 0, 4, 12, 30]
        for pivot in range(len(base)):
            rotated = base[pivot:] + base[:pivot]
            self.assertEqual(find_min_binary(rotated), find_min_linear(rotated))


if __name__ == "__main__":
    unittest.main()

Decision table

เงื่อนไข	Linear scan	Sort สำเนา	Binary search
Input เล็ก / เน้น readability	ชัดที่สุด	สั้นแต่เกินงาน	ต้องอธิบาย invariant
Input ใหญ่	O(n)	O(n log n)	O(log n)
Memory จำกัด	O(1)	O(n)	O(1)
ข้อมูลยัง sorted-rotated และไม่ซ้ำ	ไม่ใช้ประโยชน์	ไม่ใช้ประโยชน์	เหมาะสุด
Streaming input	ทำได้	ต้องเก็บครบ	ต้อง random access
ห้ามแก้ input	ได้	ได้เมื่อ sort สำเนา	ได้

Edge cases และ trade-offs

สมาชิกเดียวตอบตัวเอง; array ที่ไม่ถูกหมุนตอบสมาชิกแรก; pivot อาจอยู่ติดปลาย; จำนวนลบไม่เปลี่ยนหลักการ เงื่อนไขไม่ซ้ำสำคัญมาก หากมีค่าซ้ำ เช่น [2,2,2,0,1,2] กรณี nums[mid] == nums[right] บอกฝั่งไม่ได้ ต้องลดขอบทีละหนึ่งและ worst case กลับเป็น O(n) ซึ่งเป็นอีกโจทย์หนึ่ง

Recap

• ยืนยันก่อนว่าสมาชิกไม่ซ้ำและ array มาจากลำดับเรียงที่หมุน
• เก็บ mid ไว้เมื่อมันอาจเป็น minimum ด้วย right = mid
• ใช้ linear เป็น oracle สำหรับ property tests ขนาดเล็ก
• เลือก binary search เป็น default ภายใต้ constraints ของโจทย์