LeetCode #35 Search Insert Position: เต่า เหยี่ยว แมว ชิงตำแหน่งเสียบเลข

LeetCode #35 Search Insert Position ให้ลิสต์จำนวนเต็มที่เรียงจากน้อยไปมากและไม่มีเลขซ้ำ พร้อมเลขเป้าหมายหนึ่งตัว เราต้องคืนตำแหน่งของเลขนั้นถ้ามีอยู่ หรือคืนตำแหน่งที่ควรแทรกเพื่อให้ลิสต์ยังเรียงเหมือนเดิม โดยนับช่องแรกเป็นศูนย์และไม่ต้องแทรกจริงครับ โจทย์กำหนดเวลา O(log n) ซึ่งหมายถึงเมื่อข้อมูลโตขึ้น งานค้นหาเพิ่มช้า เพราะเราตัดตัวเลือกทิ้งได้ประมาณครึ่งหนึ่งต่อรอบ

งานจริงก็คล้ายหาว่าคะแนนของเราควรอยู่ตรงไหนในตารางที่เรียงคะแนนจากน้อยไปมากแล้ว

nums = [2, 4, 8, 11], target = 7 → output = 2
nums = [2, 4, 8, 11], target = 8 → output = 2
nums = [2, 4, 8, 11], target = 12 → output = 4

วันนี้เต่า “ต้วม” เหยี่ยว “ครึ่งฟ้า” และแมว “งีบ” มาเถียงกัน โดยมี บารอน สิงโตทะเลสวมเสื้อโค้ตเป็นกรรมการครับ

ผู้เข้าแข่งขัน

ตัวละคร	วิธี	นิสัยที่เข้ากับวิธี
เต่าต้วม 🐢	Linear scan เดินทีละช่อง	รอบคอบ ตรวจทุกช่องก่อนเดินต่อ
เหยี่ยวครึ่งฟ้า 🦅	Binary search เขียนเอง	มองภาพกว้าง ตัดพื้นที่ค้นหาทีละครึ่ง
แมวงีบ 🐱	bisect.bisect_left	ชอบใช้เครื่องมือสำเร็จรูปแล้วกลับไปนอน
บารอน 🦭	กรรมการ	ใส่เสื้อโค้ต ถือเวลา และตรวจว่าทำตามกติกา

ผมจะให้ทุกตัวตอบความหมายเดียวกัน คือ “ตำแหน่งแรกที่ค่าไม่ต่ำกว่าเป้าหมาย” ถ้าไม่มีตำแหน่งนั้นให้ตอบความยาวลิสต์ นิยามนี้ครอบคลุมทั้งค้นเจอและหาช่องแทรก จึงไม่ต้องเขียนสองงานแยกกัน

วิธีที่ 1: เต่าต้วม — Linear scan เดินทีละช่อง

“ขอผมดูทีละแฟ้ม เดี๋ยวก็เจอช่องเอง” ต้วมเดินจากซ้ายไปขวา พอเห็นเลขที่มากกว่าหรือเท่ากับเป้าหมายก็หยุดทันที เพราะเลขก่อนหน้านั้นเล็กกว่าเป้าหมายทั้งหมด ส่วนเลขหลังจากนั้นไม่มีทางให้ช่องแทรกที่อยู่ซ้ายกว่าได้

ถ้าเดินพ้นแถวแล้วยังไม่เจอ แปลว่าเป้าหมายใหญ่กว่าทุกตัว ช่องที่ต้องคืนจึงอยู่ท้ายลิสต์ เขียนเป็น len(nums) ได้เลย สำหรับลิสต์ว่าง ลูปไม่ทำงานและคืนศูนย์ตามธรรมชาติ

เป้าหมาย 7
[2, 4, 8, 11]
 ↑  ↑  ↑
ผ่าน ผ่าน หยุด: ช่อง 2 คือคำตอบ

• เวลา: O(n) ในกรณีแย่สุด หมายถึงจำนวนงานเพิ่มตามจำนวนสมาชิก n ถ้าเป้าหมายอยู่ท้ายแถวก็ต้องตรวจเกือบทุกตัว จึงไม่ผ่านเงื่อนไข O(log n) ของโจทย์
• หน่วยความจำเพิ่ม: O(1) คือใช้ตัวแปรเพิ่มจำนวนคงที่ ไม่ต้องสร้างลิสต์อีกชุดตามขนาดข้อมูล
• ข้อดี: อ่านตรงไปตรงมา ใช้เป็นคำตอบอ้างอิงตอนตรวจวิธีที่ซับซ้อนกว่าได้ และหยุดเร็วถ้าเป้าหมายอยู่ต้นลิสต์
• ข้อเสีย/edge cases: ลิสต์ยาวและเป้าหมายอยู่ท้ายทำให้ช้า ต้องใช้ >= เพื่อคืนช่องของเลขที่มีอยู่แล้ว หากใช้แค่ > จะเลยเลขที่ตรงเป้าหมายไป

ต้วมไม่ได้ไร้ประโยชน์ครับ เขาทำให้เราเห็นความหมายของคำตอบก่อนสนใจความเร็ว แต่บารอนจดไว้แล้วว่า “เข้าใจง่าย” กับ “ผ่านข้อกำหนด” เป็นคนละหัวข้อในใบให้คะแนน

วิธีที่ 2: เหยี่ยวครึ่งฟ้า — Binary search ช่วงแบบไม่รวมปลายขวา

“มองตรงกลางแล้วทิ้งฝั่งที่ใช้ไม่ได้เลย” ครึ่งฟ้าใช้ binary search หรือการค้นหาแบบแบ่งครึ่ง เริ่มด้วย lo = 0 และ hi = len(nums) ช่วงสมาชิกที่ยังต้องตรวจคือ [lo, hi) หมายถึงรวมช่อง lo แต่ไม่รวมช่อง hi ครับ

จุดที่ต้องจำคือ สมาชิกที่ยังไม่ตรวจ อยู่ใน [lo, hi) ส่วน ตำแหน่งคำตอบ ยังเป็นปลายขวา hi ได้ เช่นช่องต่อท้ายลิสต์ เราจึงให้ hi เริ่มที่ความยาวได้ แต่จะไม่หยิบ nums[hi] มาอ่าน

แต่ละรอบคำนวณ mid ซึ่งเป็นช่องกลาง ถ้า nums[mid] < target สมาชิกตั้งแต่ต้นจนถึง mid เล็กเกินไปทั้งหมด จึงเลื่อน lo ไป mid + 1 หากค่าเท่ากับหรือใหญ่กว่าเป้าหมาย ให้เลื่อน hi มา mid เพื่อเก็บโอกาสที่ช่องกลางจะเป็นคำตอบ แล้วตรวจว่ามีช่องที่เหมาะกว่าทางซ้ายหรือไม่

nums = [2, 4, 8, 11], target = 7
lo=0, hi=4 → mid=2, ค่า 8 → hi=2
lo=0, hi=2 → mid=1, ค่า 4 → lo=2
lo=2, hi=2 → หยุดและคืน 2

เหตุผลที่ไว้ใจวิธีนี้ได้คือ ก่อน lo ทุกค่าจะเล็กกว่าเป้าหมาย ส่วนตั้งแต่ hi ไปทางขวาทุกค่าจะไม่เล็กกว่าเป้าหมาย เมื่อสองขอบชนกันจึงไม่มีพื้นที่ให้สงสัยเหลือ และ lo เป็นรอยต่อพอดี คุณสมบัติที่ยังจริงอยู่ทุกรอบแบบนี้เรียกว่า invariant หรือกติกาที่รักษาไว้ระหว่างลูป

ครึ่งฟ้าไม่รีบคืนค่าทันทีเมื่อเจอเลขเท่ากัน เพราะอยากรักษาความหมาย “ช่องแรกที่ไม่ต่ำกว่าเป้าหมาย” ไว้ตลอด ในโจทย์ที่เลขไม่ซ้ำจะคืนตอนเจอเลยก็ได้ แต่รูปแบบนี้ทำให้รองรับเลขซ้ำเพิ่มเติมได้โดยไม่ต้องเปลี่ยนวิธีคิด

• เวลา: O(log n) เพราะลดช่วงที่ต้องตรวจประมาณครึ่งหนึ่งทุกรอบ เป็นวิธีที่ผ่านข้อกำหนดของโจทย์
• หน่วยความจำเพิ่ม: O(1) เก็บเพียงขอบซ้าย ขอบขวา และช่องกลาง ใช้ลูปจึงไม่มีหน่วยความจำจากการเรียกฟังก์ชันซ้อนตามความลึก
• ข้อดี: อธิบายความถูกต้องได้ ควบคุมเงื่อนไขเอง และย้ายแนวคิดไปภาษาที่ไม่มี bisect ได้สะดวก
• ข้อเสีย/edge cases: สลับกติกาของขอบง่าย หากใช้ hi = mid - 1 กับช่วงแบบนี้อาจตัดคำตอบทิ้ง ถ้าใช้ lo = mid ก็อาจไม่คืบหน้า ต้องใช้คู่การอัปเดตให้ตรงกับนิยามช่วง

ลิสต์ว่างทำให้ lo == hi ตั้งแต่ต้น จึงคืนศูนย์โดยไม่อ่านสมาชิก เป้าหมายเล็กกว่าทั้งหมดจะได้ศูนย์ ส่วนเป้าหมายใหญ่กว่าทั้งหมดจะได้ len(nums) เลขติดลบไม่ต้องมีเงื่อนไขพิเศษ เพราะใช้การเปรียบเทียบตามลำดับปกติ

วิธีที่ 3: แมวงีบ — ใช้ bisect_left ให้ตรงความหมาย

“เครื่องมือทำไว้แล้ว ผมขอนอนต่อได้ไหม” งีบใช้ bisect_left(nums, target) จากไลบรารีมาตรฐาน Python ฟังก์ชันนี้คืนตำแหน่งที่แบ่งฝั่งซ้ายให้มีแต่ค่าที่เล็กกว่าเป้าหมาย และฝั่งขวาเป็นค่าที่มากกว่าหรือเท่ากับเป้าหมาย จึงตรงกับคำตอบที่เราต้องการพอดี

ชื่อ bisect หมายถึงแบ่งเป็นสองส่วน มันยังค้นหาแบบแบ่งครึ่งเหมือนครึ่งฟ้า เพียงย้ายรายละเอียดเรื่องขอบไปอยู่ในฟังก์ชันที่เตรียมมาให้ อ่านสัญญาของฟังก์ชันได้ใน Python docs — bisect โดยไม่ต้องติดตั้งแพ็กเกจเพิ่มครับ

bisect_left กับ bisect_right ต่างกันตรงการวางเป้าหมายที่เท่ากับสมาชิกเดิม ตัวแรกวางก่อนกลุ่มเลขที่เท่ากัน ส่วนตัวหลังวางหลังก้อนนั้น หากเป้าหมายไม่อยู่ในลิสต์ ผลจะเหมือนกัน จุดที่แยกผลคือมีค่าที่เท่ากัน โดยเฉพาะกลุ่มเลขซ้ำ แม้โจทย์นี้ไม่มีสมาชิกซ้ำ แต่เมื่อค้นพบเป้าหมายอยู่แล้ว bisect_right ก็จะคืนช่องถัดจากมัน ไม่ใช่ดัชนีที่โจทย์ขอ

nums = [2, 4, 4, 9], target = 4
bisect_left  → 1  (ก่อนเลข 4 ตัวแรก)
bisect_right → 3  (หลังเลข 4 ตัวสุดท้าย)

nums = [2, 4, 9], target = 4
bisect_left  → 1
bisect_right → 2

• เวลา: O(log n) สำหรับการค้นหาบนลิสต์ จึงผ่านเงื่อนไขเวลาเหมือนวิธีเหยี่ยว
• หน่วยความจำเพิ่ม: O(1) สำหรับงานค้นหานี้ ไม่มีการคัดลอกลิสต์
• ข้อดี: สั้น อ่านง่ายเมื่อรู้ความหมายของฟังก์ชัน และบน CPython มีส่วนค้นหาที่ทำงานในภาษา C จึงลดภาระลูป Python
• ข้อเสีย/edge cases: ต้องเลือก left ให้ถูก และลิสต์ต้องเรียงอยู่ก่อน การส่งข้อมูลที่ยังไม่เรียงเข้าไปไม่ได้ทำให้ฟังก์ชันจัดเรียงให้

งีบย้ำว่า bisect_left แค่คืนเลขช่อง มันไม่ได้แทรกสมาชิก ส่วนการแทรกจริงลง Python list อาจต้องขยับสมาชิกจำนวนมากและใช้เวลา O(n) การค้นหาที่เร็วจึงไม่ได้รับประกันว่ากระบวนการค้นหาแล้วแทรกทั้งหมดจะเร็วแบบเดียวกัน

โค้ดทุกวิธี พร้อมเทสต์

โค้ดนี้ใช้เฉพาะไลบรารีมาตรฐาน บันทึกเป็น search_insert.py แล้วรัน python3 -I -B search_insert.py ได้เลย ALL รวมทุกวิธีไว้ให้ชุดทดสอบเดียวกันวนตรวจ จึงไม่มีตัวไหนได้ข้ามกรณีขอบครับ

กรณีว่างและเลขซ้ำเป็นการทดสอบความทนทานเพิ่มจากข้อมูลตามโจทย์ สำหรับเลขซ้ำเราตั้งใจคืนช่องซ้ายสุด เทสต์ยังตรวจว่าลิสต์ไม่เปลี่ยนหลังค้นหา และไล่เป้าหมายผ่านทุกช่องว่างในลิสต์ขนาดเล็ก โดยนับจำนวนค่าที่เล็กกว่าเป้าหมายเป็นคำตอบอ้างอิง

import unittest
from bisect import bisect_left


def turtle_scan(nums, target):
    for i, value in enumerate(nums):
        if value >= target:
            return i
    return len(nums)


def hawk_binary(nums, target):
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo


def cat_bisect(nums, target):
    return bisect_left(nums, target)


ALL = [turtle_scan, hawk_binary, cat_bisect]


class SearchInsertTests(unittest.TestCase):
    def test_examples_and_edges(self):
        cases = [
            ([1, 3, 5, 6], 5, 2),
            ([1, 3, 5, 6], 2, 1),
            ([1, 3, 5, 6], 7, 4),
            ([1, 3, 5, 6], 0, 0),
            ([4], 4, 0),
            ([4], 3, 0),
            ([4], 5, 1),
            ([-8, -3, 0, 7], -4, 1),
            ([-8, -3, 0, 7], -3, 1),
            ([], 10, 0),
            ([1, 2, 2, 2, 5], 2, 1),
        ]
        for solve in ALL:
            for nums, target, expected in cases:
                with self.subTest(method=solve.__name__, nums=nums,
                                  target=target):
                    before = nums.copy()
                    self.assertEqual(solve(nums, target), expected)
                    self.assertEqual(nums, before)

    def test_every_gap_in_small_arrays(self):
        for n in range(20):
            nums = list(range(-n, n, 2))
            for target in range(-n - 1, n + 2):
                expected = sum(value < target for value in nums)
                for solve in ALL:
                    with self.subTest(method=solve.__name__, n=n,
                                      target=target):
                        self.assertEqual(solve(nums, target), expected)


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

รันบนเครื่องนี้แล้วผ่านทั้งสองเมธอดทดสอบ โดยแต่ละเมธอดตรวจหลายกรณีผ่าน subTest การผ่านเทสต์ช่วยจับปัญหาขอบได้ ส่วนเหตุผลเรื่องรอยต่อของ lo กับ hi ยังจำเป็นสำหรับอธิบายว่าทำไมวิธีแบ่งครึ่งจึงถูกต้องในกรณีทั่วไป

Benchmark ที่รันจริง (20 ต.ค. 2026 บนเครื่องนี้)

ผมใช้ Python 3.14.7 จาก python3 -V และสถาปัตยกรรม x86_64 จาก platform.machine() รันสคริปต์ด้วย python3 -I -B ใช้ Python docs — timeit เป็นแนวทางวัดด้วย timeit.repeat โดยตั้ง repeat=5, number=1 แล้วเลือกค่าต่ำสุดจากห้ารอบ หรือ best of 5

แต่ละขนาดสร้าง nums = list(range(0, 2 * n, 2)) และเป้าหมาย 128 ตัวจากสูตร -1 + (2 * n + 2) * i // 127 สำหรับ i ตั้งแต่ 0 ถึง 127 จึงมีการค้นหาที่กระจายตลอดลิสต์ รวมทั้งต่ำกว่าค่าต่ำสุดและสูงกว่าค่าสูงสุด ทุกวิธีใช้ข้อมูลกับเป้าหมายชุดเดียวกันของขนาดนั้น สร้างข้อมูลนอกช่วงจับเวลา แล้วจับเวลาลูปที่เรียกฟังก์ชันครบทั้งชุด

วิธี	n = 1,000: ms ต่อ 128 คำค้น	n = 1,000,000: ms ต่อ 128 คำค้น
เต่าต้วม: linear scan	1.257	1230.649
เหยี่ยวครึ่งฟ้า: binary search	0.072	0.158
แมวงีบ: bisect_left	0.013	0.025

ต้วมช้าลงมากเมื่อข้อมูลใหญ่ เพราะคำค้นที่กระจายตลอดแถวทำให้ต้องเดินผ่านสมาชิกจำนวนมากซ้ำ ๆ ส่วนครึ่งฟ้ากับงีบตัดช่วงค้นหาทีละครึ่ง จึงเพิ่มงานน้อยกว่าเมื่อขยายข้อมูล แมวงีบชนะทั้งสองขนาดบนเครื่องนี้ เพราะ CPython ทำส่วนค้นหาของ bisect_left ในภาษา C ขณะที่ครึ่งฟ้ายังวนลูปและคำนวณขอบใน Python ตัวเลขเหล่านี้เป็นของเครื่องนี้และชุดคำค้นนี้เท่านั้น โดยคอลัมน์เป็นเวลารวมของหลายคำค้น ไม่ใช่เวลาต่อการค้นหาหนึ่งครั้งครับ

การเลือกค่าต่ำสุดช่วยลดผลจากรอบที่เครื่องถูกรบกวน แต่ไม่ได้แทนการวัดภาระงานจริงทั้งหมด หากงานของเราเจอเป้าหมายต้นลิสต์เป็นส่วนใหญ่ หรือมีการแก้ข้อมูลระหว่างค้นหา ก็ควรสร้างชุดวัดให้เหมือนงานนั้นก่อนตัดสินใจ

ตารางเลือกวิธีตามสถานการณ์

สถานการณ์	เลือก	เหตุผล
สัมภาษณ์ไวท์บอร์ด	เหยี่ยวครึ่งฟ้า	แสดงการแบ่งครึ่งและอธิบายขอบได้ครบตาม O(log n)
โค้ดงานจริงที่เป็น hot path (production)	แมวงีบ	ส่วนที่ถูกเรียกบ่อยได้ประโยชน์จากฟังก์ชันมาตรฐานที่เร็วที่สุดในการวัดนี้ แล้ววัดซ้ำด้วยข้อมูลจริง
สอนมือใหม่	เต่าต้วม แล้วต่อด้วยเหยี่ยว	เริ่มจากความหมายของช่องแทรก ก่อนชี้ว่าการรู้ว่าข้อมูลเรียงช่วยตัดงานได้อย่างไร
ภาษาที่ไม่มี bisect	เหยี่ยวครึ่งฟ้า	เขียนลูปแบ่งครึ่งจากกติกาขอบเดิมได้ โดยไม่ผูกกับชื่อฟังก์ชัน Python
ข้อมูลเปลี่ยนบ่อย	แมวงีบสำหรับค้นหา และประเมินต้นทุนแทรกแยก	ถ้ายังใช้ลิสต์เรียง การค้นหาเร็วแต่การขยับสมาชิกตอนแทรกอาจเป็นงานหลัก
หน่วยความจำเพิ่มมีจำกัด	เหยี่ยวหรือแมว	ทั้งคู่ใช้พื้นที่เพิ่มคงที่และผ่านข้อกำหนดเวลา

ค่าเริ่มต้นภายใต้กติกาของโจทย์: ใช้ bisect_left เมื่ออนุญาตไลบรารีมาตรฐาน และใช้ binary search แบบ [lo, hi) เมื่อต้องแสดงวิธีทำเอง

ข้อกำหนดว่าข้อมูลเรียงแล้วเป็นหัวใจของคำแนะนำนี้ครับ หากข้อมูลเปลี่ยนจนลำดับเสีย ต้องทำให้เงื่อนไขกลับมาจริงก่อนค้นหา การเรียงใหม่ทุกคำค้นก็มีต้นทุนของมัน ซึ่งไม่ได้รวมใน benchmark เพราะโจทย์ส่งข้อมูลที่เรียงไว้แล้วมาให้

บารอนสรุป

บารอนกระชับเสื้อโค้ตแล้วเคาะโต๊ะว่า “ถ้วยความเร็วรอบนี้เป็นของแมวงีบ ทั้งลิสต์เล็กและลิสต์ใหญ่ แต่เจ้าต้องรู้ด้วยว่า left คืนรอยต่อฝั่งไหน” เหยี่ยวครึ่งฟ้าได้ตำแหน่งตัวแทนอธิบายบนไวท์บอร์ด เพราะทำตาม O(log n) และชี้เหตุผลของทุกการเลื่อนขอบได้ ต้วมช่วยปูพื้นกับตรวจคำตอบได้ดี แต่ผมให้ผ่านกติกาเวลาไม่ได้ แมวงีบชนะจากผลที่วัดบนเครื่องนี้ ส่วนวันที่ต้องแทรกแฟ้มจริงบ่อย ๆ ทุกตัวต้องกลับมาดูต้นทุนขยับแฟ้มด้วยครับ

Recap

• เขียนความหมายคำตอบว่าเป็นช่องแรกที่ค่าไม่ต่ำกว่าเป้าหมาย
• ลองเดินแบบเต่ากับเป้าหมายที่เล็กกว่าทั้งหมดและใหญ่กว่าทั้งหมด
• วาดช่วง [lo, hi) แล้วอธิบายว่าทำไมไม่อ่าน nums[hi]
• ไล่ลูปเหยี่ยวด้วยมือ และตรวจว่าช่วงแคบลงทุกครั้ง
• ทดลองเลขซ้ำเพื่อเห็นความต่างระหว่าง bisect_left กับ bisect_right
• รันเทสต์ทุกวิธี และวัดเวลาซ้ำด้วยชุดคำค้นที่เหมือนงานของตัวเอง