LeetCode 33: ค้นหาใน Array ที่หมุนแล้ว เลือก Linear หรือ Binary ดี

โจทย์ Search in Rotated Sorted Array ให้ array จำนวนเต็มที่เคยเรียงเพิ่มขึ้นแบบไม่ซ้ำ แล้วถูกหมุนที่ตำแหน่งหนึ่ง เช่นลำดับเล็กถูกย้ายไปต่อท้าย เราต้องคืน index ของ target หรือ -1 หากไม่พบ โดยเป้าหมายหลักคือเวลา O(log n)

WHY: Binary Search ยังใช้ได้ เพราะอย่างน้อยครึ่งหนึ่งยังเรียง

array ทั้งก้อนไม่เรียงจากซ้ายไปขวา แต่ทุกครั้งที่แบ่งกลาง อย่างน้อยฝั่งซ้ายหรือขวาหนึ่งฝั่งยังเรียงสมบูรณ์ครับ เหมือนชั้นหนังสือเรียง A–Z ที่ถูกตัดแล้วย้ายหัวมาต่อท้าย เราไม่รู้รอยต่อทันที แต่ครึ่งหนึ่งของชั้นยังอ่านทิศได้เสมอ

วิธี 1: สแกนตรง

เดินจากซ้ายไปขวาจนเจอ target เวลา O(n), พื้นที่ O(1) อ่านง่ายและถูกต้องแม้ข้อมูลมีค่าซ้ำหรือไม่รักษาเงื่อนไข sorted เหมาะกับ input เล็กหรือข้อมูล streaming ที่เก็บ array ไม่ครบ แต่ไม่ผ่านเป้าหมาย O(log n)

วิธี 2: หา Pivot แล้ว Binary Search

ใช้ binary search แรกหารายการที่เล็กสุดหรือจุดหมุน จากนั้นเลือกครึ่งที่ target อยู่และใช้ binary search ปกติ เวลา O(log n), พื้นที่ O(1) ข้อดีคือแยกสองแนวคิดชัดและนำ pivot ไปใช้ต่อได้ ข้อเสียคือมีสองรอบและ boundary มากขึ้น

วิธี 3: One-pass Modified Binary Search

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

import unittest


def linear_search(nums, target):
    for index, value in enumerate(nums):
        if value == target:
            return index
    return -1


def ordinary_binary(nums, target, left, right):
    while left <= right:
        middle = (left + right) // 2
        if nums[middle] == target:
            return middle
        if nums[middle] < target:
            left = middle + 1
        else:
            right = middle - 1
    return -1


def pivot_search(nums, target):
    if not nums:
        return -1
    left, right = 0, len(nums) - 1
    while left < right:
        middle = (left + right) // 2
        if nums[middle] > nums[right]:
            left = middle + 1
        else:
            right = middle
    pivot = left
    if target <= nums[-1]:
        return ordinary_binary(nums, target, pivot, len(nums) - 1)
    return ordinary_binary(nums, target, 0, pivot - 1)


def one_pass_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        middle = (left + right) // 2
        if nums[middle] == target:
            return middle
        if nums[left] <= nums[middle]:
            if nums[left] <= target < nums[middle]:
                right = middle - 1
            else:
                left = middle + 1
        else:
            if nums[middle] < target <= nums[right]:
                left = middle + 1
            else:
                right = middle - 1
    return -1


class SearchTests(unittest.TestCase):
    def test_all_methods(self):
        cases = [
            ([4, 5, 6, 7, 0, 1, 2], 0, 4),
            ([4, 5, 6, 7, 0, 1, 2], 3, -1),
            ([1], 1, 0),
            ([3, 1], 1, 1),
            ([], 9, -1),
        ]
        for method in (linear_search, pivot_search, one_pass_search):
            for nums, target, expected in cases:
                with self.subTest(method=method.__name__, nums=nums):
                    self.assertEqual(method(nums, target), expected)


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

Decision Table

สภาพ input	สแกนตรง	Pivot + Binary	One-pass Binary
ขนาดเล็ก/อ่านง่ายสำคัญ	ดีที่สุด	เกินจำเป็น	ใช้ได้
ขนาดใหญ่ตาม constraints	ช้า O(n)	ดี O(log n)	ดีที่สุด O(log n)
memory จำกัด	O(1)	O(1)	O(1)
sorted แล้วหมุน, ค่าไม่ซ้ำ	ไม่ใช้คุณสมบัติ	ใช้เต็มที่	ใช้เต็มที่
streaming หรือเงื่อนไขไม่แน่นอน	เหมาะกว่า	ไม่เหมาะ	ไม่เหมาะ
ห้ามแก้ input	ผ่าน	ผ่าน	ผ่าน

Edge Cases และ Trade-offs

array ว่าง, สมาชิกเดียว, ไม่หมุน, หมุนเกือบสุด และ target ตรง pivot ต้องผ่านทั้งหมด เงื่อนไข “ค่าไม่ซ้ำ” สำคัญ หากมี duplicate การดูว่าครึ่งไหนเรียงอาจกำกวมและต้องลด boundary ทีละหนึ่งจน worst case O(n)

best default คือ one-pass binary search เพราะตรง O(log n), O(1) และไม่ mutate input ถ้าสัมภาษณ์แล้วอยากลดความผิดพลาด เริ่มอธิบาย invariant ว่า “ก่อนทุก loop ถ้า target มีอยู่ มันอยู่ระหว่าง left กับ right” แล้วค่อยเขียน branch

Recap

• array หมุนยังมีอย่างน้อยหนึ่งครึ่งที่เรียง
• ใช้ช่วงค่าตัดสินว่า target อยู่ในครึ่งเรียงหรือไม่
• ระวัง inclusive boundary
• duplicate ทำให้ worst case ลดเป็น O(n)
• เลือก one-pass เป็นค่าเริ่มต้นภายใต้ constraints