การค้นหาแบบไบนารีทำงานอย่างไร และต้องการอะไร?

Question

Accepted Answer

**การค้นหาแบบไบนารี** ค้นหาเป้าหมายในอาร์เรย์ที่**เรียงลำดับแล้ว**โดยการแบ่งช่วงการค้นหาครึ่งหนึ่งซ้ำ ๆ การเปรียบเทียบแต่ละครั้งจะกำจัดองค์ประกอบที่เหลือครึ่งหนึ่ง ให้เวลา **O(log n)** ## ความคิด ดูองค์ประกอบตรงกลาง หากเท่ากับเป้าหมายแล้วเสร็จ หากเป้าหมายเล็กกว่า ให้ค้นหาครึ่งซ้าย หากใหญ่กว่า ให้ค้นหาครึ่งขวา ทำซ้ำจนกว่าจะพบหรือช่วงว่างเปล่า ## ตัวอย่าง ```python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 # middle index if arr[mid] == target: return mid # found it elif arr[mid] < target: lo = mid + 1 # discard left half else: hi = mid - 1 # discard right half return -1 # not present binary_search([1, 3, 5, 7, 9], 7) # -> 3 ``` ## การติดตาม ```text Search 7 in [1,3,5,7,9] lo=0 hi=4 mid=2 -> 5 < 7 => lo=3 lo=3 hi=4 mid=3 -> 7 == 7 => return 3 ``` ## ความซับซ้อน - **เวลา:** O(log n). **พื้นที่:** O(1) แบบวนซ้ำ ## ข้อผิดพลาด **อินพุตต้องเรียงลำดับแล้ว** — มิฉะนั้นผลลัพธ์จะไม่มีความหมาย ระวังข้อผิดพลาด off-by-one ใน `lo`/`hi` และ integer overflow ในบางภาษา (ใช้ `lo + (hi-lo)//2`) ## เหตุใดจึงสำคัญ การแบ่งครึ่งพื้นที่การค้นหาจะเปลี่ยนการค้นหาในอาร์เรย์ที่มีหนึ่งล้านองค์ประกอบเป็น ~20 การเปรียบเทียบ รูปแบบ divide-and-conquer เบื้องหลังมันปรากฏขึ้นซ้ำในต้นไม้ ฐานข้อมูล และปัญหาการสัมภาษณ์นับไม่ถ้วน การรู้ข้อกำหนดที่เข้มงวดหนึ่งข้อ — อินพุตที่เรียงลำดับแล้ว — จะทำให้คุณหลีกเลี่ยงข้อบกพร่องแบบละเอียดแบบคลาสสิก