การค้นหาแบบทวิภาคคลาสสิก: ซ้าย ขวา กลาง
สร้างการค้นหาแบบทวิภาคทั้งแบบวนซ้ำและแบบเรียกซ้ำ จัดการรายละเอียดการคลาดเคลื่อนทีละหนึ่งของขอบเขต lo/hi และตรวจสอบความถูกต้องด้วยข้อมูลนำเข้ากรณีขอบ
การค้นหาแบบทวิภาคคลาสสิก: ซ้าย ขวา กลาง เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
เหตุใดการค้นหาแบบทวิภาคจึงสำคัญ
การค้นหาแบบทวิภาค ลดการสแกนเชิงเส้นที่ใช้เวลา O(n) ให้เหลือ O(log n) ด้วยการแบ่งพื้นที่ค้นหาครึ่งหนึ่งในทุกขั้นตอน ในอาร์เรย์ที่มีสมาชิกหนึ่งล้านตัว การสแกนเชิงเส้นอาจต้องเปรียบเทียบถึง 1,000,000 ครั้ง แต่การค้นหาแบบทวิภาคต้องเปรียบเทียบไม่เกิน 20 ครั้ง ประสิทธิภาพนี้ทำให้การค้นหาแบบทวิภาคเป็นหนึ่งในอัลกอริทึมที่ถูกทดสอบบ่อยที่สุดในการสัมภาษณ์การเขียนโปรแกรม
แนวคิดสำคัญคือ อาร์เรย์ที่เรียงลำดับแล้ว ช่วยให้ตัดสินใจได้หลังจากการเปรียบเทียบเพียงครั้งเดียวว่าจะทิ้งข้อมูลครึ่งใดของข้อมูลที่เหลือทั้งหมด
กรอบแนวคิดซ้าย กลาง ขวา
การค้นหาแบบทวิภาคใช้ตัวชี้ดัชนีสามตัว ได้แก่ lo (ขอบเขตซ้าย) hi (ขอบเขตขวา) และ mid (จุดกึ่งกลาง) ในแต่ละรอบ ให้คำนวณ mid = (lo + hi) // 2 แล้วเปรียบเทียบค่าเป้าหมายกับ arr[mid] หากค่าเป้าหมายเล็กกว่า ให้เลื่อน hi = mid - 1 หากใหญ่กว่า ให้เลื่อน lo = mid + 1 หากเท่ากัน แสดงว่าพบค่าแล้ว
ลูปจะทำงานต่อขณะที่ lo <= hi เมื่อจบลูปโดยไม่พบค่าเป้าหมาย ให้คืนค่า -1
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
print(binary_search([1, 3, 5, 7, 9, 11], 7)) # 3
print(binary_search([1, 3, 5, 7, 9, 11], 6)) # -1หลีกเลี่ยงจำนวนเต็มล้นในการคำนวณ Mid
นิพจน์ mid = (lo + hi) // 2 อาจทำให้เกิดจำนวนเต็มล้นในภาษาที่ใช้จำนวนเต็มความกว้างคงที่ (Java, C++) จำนวนเต็มของ Python มีความละเอียดได้ตามต้องการ จึงไม่เกิดการล้น แต่ผู้สัมภาษณ์ยังคาดหวังให้ทราบทางเลือกที่ปลอดภัย: mid = lo + (hi - lo) // 2
รูปแบบนี้คำนวณจุดกึ่งกลางเดียวกัน แต่เพิ่มเพียงครึ่งหนึ่งของระยะห่างเข้าไปใน lo แทนที่จะนำตัวชี้ทั้งสองมาบวกกันก่อน การกล่าวถึงเรื่องนี้ในการสัมภาษณ์แสดงให้เห็นถึงความตระหนักในข้อควรคำนึงระดับล่าง
# Safe mid calculation (important in Java/C++, good habit in Python too)
lo, hi = 0, 1_000_000_000
mid_unsafe = (lo + hi) // 2 # fine in Python
mid_safe = lo + (hi - lo) // 2 # same result, no overflow risk
print(mid_unsafe == mid_safe) # Trueขอบเขตแบบรวมกับแบบไม่รวม
ส่วนที่ยากที่สุดอย่างหนึ่งของการค้นหาแบบทวิภาคคือการเลือกว่าจะให้ hi ชี้ไปยัง ดัชนีสุดท้ายที่ถูกต้อง (แบบรวมขอบเขต, hi = len(arr) - 1) หรือชี้ไปยังตำแหน่งถัดจากจุดสิ้นสุด (แบบไม่รวมขอบเขต, hi = len(arr)) รูปแบบที่ต่างกันต้องใช้เงื่อนไขลูปและการปรับขอบเขตที่ต่างกัน
เมื่อใช้ขอบเขตแบบ รวม ให้ใช้ while lo <= hi และปรับเป็น hi = mid - 1 เมื่อใช้ขอบเขตแบบ ไม่รวม ให้ใช้ while lo < hi และปรับเป็น hi = mid การผสมรูปแบบเข้าด้วยกันเป็นสาเหตุที่พบบ่อยที่สุดของข้อผิดพลาดในการเขียนการค้นหาแบบทวิภาค
# Exclusive hi variant — useful for bisect-style lower-bound
def search_exclusive(arr, target):
lo, hi = 0, len(arr) # hi is one past last
while lo < hi: # strictly less than
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid # NOT mid - 1
return lo if lo < len(arr) and arr[lo] == target else -1
print(search_exclusive([2, 4, 6, 8, 10], 6)) # 2การค้นหาแบบทวิภาคด้วยการเรียกซ้ำ
สามารถเขียนการค้นหาแบบทวิภาคในรูปแบบ เรียกซ้ำ ได้ โดยส่งขอบเขต lo และ hi ที่ปรับปรุงแล้วผ่านกองการเรียกใช้ แต่ละการเรียกซ้ำจะลดพื้นที่ค้นหาลงครึ่งหนึ่ง ดังนั้นความลึกจึงเป็น O(log n) กรณีฐานคือเมื่อ lo > hi (ไม่พบ) หรือ arr[mid] == target (พบ)
ในโค้ดที่ใช้งานจริงมักเลือกใช้รูปแบบวนซ้ำ เพราะหลีกเลี่ยงค่าใช้จ่ายของเฟรมกองการเรียกใช้ได้ แต่รูปแบบเรียกซ้ำสื่อโครงสร้างแบบแบ่งแล้วพิชิตได้ชัดเจนกว่าเมื่ออธิบายบนกระดาน
def binary_search_rec(arr, target, lo, hi):
if lo > hi:
return -1
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_rec(arr, target, mid + 1, hi)
else:
return binary_search_rec(arr, target, lo, mid - 1)
arr = [1, 3, 5, 7, 9, 11]
print(binary_search_rec(arr, 9, 0, len(arr) - 1)) # 4กรณีขอบ: อาร์เรย์ว่างและสมาชิกเดียว
การค้นหาแบบทวิภาคที่แข็งแกร่งต้องจัดการกรณีขอบได้โดยไม่หยุดทำงานผิดพลาด กรณีที่พบบ่อยที่สุดมีสามกรณี ได้แก่ อาร์เรย์ว่าง (ลูปไม่ทำงานเลยและคืนค่า -1 ได้อย่างถูกต้อง) อาร์เรย์ที่มีสมาชิกเดียว (mid เท่ากับ lo และเท่ากับ hi การเปรียบเทียบเพียงครั้งเดียวก็เพียงพอ) และ ค่าเป้าหมายนอกช่วง (ในที่สุด lo จะมากกว่า hi และคืนค่า -1)
ควรตรวจสอบการเขียนของตนเองกับข้อมูลนำเข้าเหล่านี้เสมอ ก่อนเข้าสู่คำถามต่อยอดในการสัมภาษณ์
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
print(binary_search([], 5)) # -1 (empty)
print(binary_search([7], 7)) # 0 (single, found)
print(binary_search([7], 3)) # -1 (single, not found)
print(binary_search([1,3,5], 0)) # -1 (below range)
print(binary_search([1,3,5], 9)) # -1 (above range)ความซับซ้อนด้านเวลาและพื้นที่
การค้นหาแบบทวิภาคมีความซับซ้อนด้านเวลาเป็น O(log n) เพราะการเปรียบเทียบแต่ละครั้งแบ่งพื้นที่ค้นหาครึ่งหนึ่ง หลังจากเปรียบเทียบ k ครั้ง พื้นที่ที่เหลือคือ n/2^k การค้นหาจะจบลงเมื่อค่านี้เหลือ 1 ดังนั้น k = log₂ n
ความซับซ้อนด้านพื้นที่คือ O(1) สำหรับรูปแบบวนซ้ำ (ใช้ตัวแปรจำนวนเต็มเพียงสามตัว) และ O(log n) สำหรับรูปแบบเรียกซ้ำ เนื่องจากความลึกของกองการเรียกใช้ ในการสัมภาษณ์ควรระบุทั้งสองค่าเสมอ และเลือกใช้รูปแบบวนซ้ำเมื่อพื้นที่มีข้อจำกัด
import math
for n in [10, 100, 1000, 1_000_000, 1_000_000_000]:
steps = math.ceil(math.log2(n + 1))
print(f'n={n:>12,} max comparisons={steps}')ค้นหาค่าที่ตรงกันทุกประการเทียบกับค้นหาขอบเขต
การค้นหาแบบทวิภาคแบบคลาสสิกจะคืนค่า ดัชนีใดก็ได้ ที่มีค่าเป้าหมายอยู่ แต่โจทย์สัมภาษณ์จำนวนมากต้องการ ตำแหน่งแรก หรือ ตำแหน่งสุดท้าย ที่พบค่าเป้าหมาย ในกรณีเหล่านี้ต้องค้นหาต่อแม้จะพบค่าที่ตรงกันแล้ว แทนที่จะคืนค่าทันที ให้บีบขอบเขตและค้นหาต่อ
เมื่อค้นหาตำแหน่งแรก หลังพบว่า arr[mid] == target ให้บันทึก mid เป็นตัวเลือก แล้วกำหนด hi = mid - 1 สำหรับตำแหน่งสุดท้าย ให้กำหนด lo = mid + 1
def first_occurrence(arr, target):
lo, hi, result = 0, len(arr) - 1, -1
while lo <= hi:
mid = lo + (hi - lo) // 2
if arr[mid] == target:
result = mid
hi = mid - 1 # keep searching left
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return result
print(first_occurrence([1, 2, 2, 2, 3], 2)) # 1การใช้โมดูล bisect ของ Python
ไลบรารีมาตรฐานของ Python มี bisect.bisect_left(arr, x) และ bisect.bisect_right(arr, x) สำหรับการค้นหาแบบทวิภาคที่พร้อมใช้จริง bisect_left จะคืนค่าดัชนีซ้ายสุดที่สามารถแทรก x เพื่อให้อาร์เรย์ยังเรียงลำดับอยู่ หรือเทียบเท่ากับการค้นหาตำแหน่งแรกที่ arr[i] >= x
ผู้สัมภาษณ์อาจอนุญาตให้ใช้ bisect ได้ แต่ควรยืนยันก่อนเสมอ ถึงอย่างนั้น การรู้ว่ามันทำงานเบื้องหลังอย่างไร (เป็นการค้นหาแบบทวิภาคที่ใช้เวลา O(log n)) ก็ยังเป็นสิ่งจำเป็น
import bisect
arr = [1, 2, 2, 2, 3, 5]
print(bisect.bisect_left(arr, 2)) # 1 (first 2)
print(bisect.bisect_right(arr, 2)) # 4 (after last 2)
# Check if target exists
target = 3
idx = bisect.bisect_left(arr, target)
print(idx < len(arr) and arr[idx] == target) # Trueข้อผิดพลาดที่พบบ่อยในการค้นหาแบบทวิภาค
ข้อผิดพลาดสามประการทำให้เกิดปัญหาส่วนใหญ่ในการค้นหาแบบทวิภาคระหว่างการสัมภาษณ์ ประการแรกคือ เงื่อนไขลูปไม่ถูกต้อง: การใช้ < แทน <= กับขอบเขตแบบรวมจะทำให้ข้ามสมาชิกสุดท้ายที่เหลืออยู่ ประการที่สองคือ การปรับขอบเขตไม่ถูกต้อง: การลืม +1 หรือ -1 จะทำให้เกิดลูปไม่รู้จบเมื่อ lo == hi ประการที่สามคือ การทำงานกับอาร์เรย์ที่ไม่ได้เรียงลำดับ: การค้นหาแบบทวิภาคถูกต้องเฉพาะกับข้อมูลที่เรียงลำดับแล้วเท่านั้น
ก่อนเขียนการค้นหาแบบทวิภาค ควรพูดออกมาเสมอว่า ‘อาร์เรย์เรียงลำดับแล้ว ขอบเขตของฉันเป็นแบบรวม และลูปทำงานขณะที่ lo <= hi’
# BUG: infinite loop when lo == hi because hi = mid never moves past lo
def buggy(arr, target):
lo, hi = 0, len(arr) - 1
while lo < hi: # should be lo <= hi for exact-match
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid # stops, but never returns mid when found
return lo if arr[lo] == target else -1
print(buggy([1, 3, 5, 7], 7)) # 3 (works here by luck)
print(buggy([1, 3, 5, 7], 1)) # 0 (correct)
print(buggy([1, 3, 5, 7], 4)) # -1 (correct)เคล็ดลับการสัมภาษณ์เกี่ยวกับการค้นหาแบบทวิภาค
เมื่อพบโจทย์ที่เกี่ยวกับ อาร์เรย์ที่เรียงลำดับแล้ว ฟังก์ชันที่เพิ่มขึ้นอย่างมีทิศทางเดียว หรือพื้นที่ค้นหาที่แบ่งครึ่งได้ ให้พิจารณาการค้นหาแบบทวิภาคทันที ในการสัมภาษณ์ ควรบรรยายแนวคิดของตนเองว่า ‘เนื่องจากอาร์เรย์เรียงลำดับแล้ว ฉันจึงตัดสมาชิกออกได้ครึ่งหนึ่งต่อการเปรียบเทียบหนึ่งครั้ง ทำให้ใช้เวลา O(log n)’
ควรตรวจสอบคำตอบกับข้อมูลนำเข้าอย่างน้อยสามแบบเสมอ ได้แก่ ค่าที่อยู่ต้นอาร์เรย์ ค่าที่อยู่ท้ายอาร์เรย์ และค่าที่ไม่มีอยู่ในอาร์เรย์ การระบุความซับซ้อนล่วงหน้า เช่น ‘เวลา O(log n) พื้นที่ O(1)’ ก่อนถูกถาม แสดงให้เห็นว่ามีพื้นฐานที่แข็งแรง
ตรวจสอบความเข้าใจ
ทดสอบความเข้าใจแนวคิดโครงสร้างข้อมูลและอัลกอริทึม — การเตรียมตัวสัมภาษณ์การเขียนโปรแกรมจากบทเรียนนี้
ทบทวนบทเรียน
ในบทเรียนนี้ได้เรียนรู้ว่า การค้นหาแบบทวิภาคแบ่งพื้นที่ค้นหาครึ่งหนึ่งในแต่ละขั้นตอน จึงใช้เวลา O(log n) รูปแบบขอบเขตแบบรวมใช้ lo <= hi พร้อมการปรับ lo = mid+1 และ hi = mid-1 และ หากต้องการหาตำแหน่งแรกหรือตำแหน่งสุดท้าย ต้องค้นหาต่อหลังพบค่าที่ตรงกัน แทนที่จะคืนค่าทันที บทถัดไปจะสำรวจว่าการค้นหาแบบทวิภาคขยายไปใช้งานกับอาร์เรย์แบบหมุนและอาร์เรย์ที่ไม่ได้เรียงลำดับได้อย่างไร
คำถามที่พบบ่อย
บทเรียน “การค้นหาแบบทวิภาคคลาสสิก: ซ้าย ขวา กลาง” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “การค้นหาแบบทวิภาคคลาสสิก: ซ้าย ขวา กลาง” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “การค้นหาแบบทวิภาคคลาสสิก: ซ้าย ขวา กลาง”
สร้างการค้นหาแบบทวิภาคทั้งแบบวนซ้ำและแบบเรียกซ้ำ จัดการรายละเอียดการคลาดเคลื่อนทีละหนึ่งของขอบเขต lo/hi และตรวจสอบความถูกต้องด้วยข้อมูลนำเข้ากรณีขอบ คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน
บทเรียน “การค้นหาแบบทวิภาคคลาสสิก: ซ้าย ขวา กลาง” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- การค้นหาแบบทวิภาคคลาสสิก: ซ้าย ขวา กลาง
- การค้นหาแบบทวิภาคในอาร์เรย์ที่หมุนและไม่เรียงลำดับ
- ขอบเขตล่างและขอบเขตบน
- การค้นหาแบบทวิภาคบนช่วงคำตอบ