การค้นหาแบบทวิภาคคลาสสิกที่ไร้บั๊ก
กำหนดลูป low, high และ mid ให้ถูกต้อง
การค้นหาแบบทวิภาคคลาสสิกที่ไร้บั๊ก เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
ลดพื้นที่ค้นหาลงครึ่งหนึ่ง
การค้นหาแบบไบนารี ค้นหาค่าในรายการที่เรียงลำดับแล้วโดยลดช่วงลงครึ่งหนึ่งในแต่ละขั้นตอน ทำให้การกวาดข้อมูลแบบ O(n) ที่ช้ากลายเป็นการค้นหาแบบ O(log n) ที่รวดเร็ว
a = [1, 3, 5, 7, 9] # must be sortedการเรียงลำดับคือกฎสำคัญเพียงข้อเดียว
การค้นหาแบบไบนารีใช้ได้กับข้อมูลที่ เรียงลำดับแล้ว เท่านั้น หากรายการไม่มีลำดับ ให้เรียงลำดับก่อน มิฉะนั้นผลลัพธ์จะไม่มีความหมายและไม่ถูกต้อง
a.sort() # ascending order requiredขอบเขตสองด้าน
เริ่มด้วยตัวชี้สองตัว: low ที่ดัชนี 0 และ high ที่ดัชนีสุดท้าย หากมีเป้าหมายอยู่ เป้าหมายนั้นจะอยู่ระหว่างตัวชี้ทั้งสองเสมอ
low, high = 0, len(a) - 1หาตรงกลางอย่างปลอดภัย
คำนวณ mid เป็น low + (high - low) // 2 ใน Python จะไม่เกิดค่าล้น แต่รูปแบบนี้เป็นแนวปฏิบัติที่ปลอดภัยในทุกที่
mid = low + (high - low) // 2ผลลัพธ์สามแบบ
เปรียบเทียบ a[mid] กับเป้าหมาย คุณอาจ พบค่าแล้ว ค่านั้นอาจเล็กเกินไป หรือใหญ่เกินไป แต่ละกรณีจะลดช่วงการค้นหาแตกต่างกัน
if a[mid] == target:
return midเล็กเกินไป ให้ไปทางขวา
หาก a[mid] น้อยกว่าเป้าหมาย คำตอบต้องอยู่ทางขวา ให้เลื่อน low ไปที่ mid + 1 แล้วตัดครึ่งซ้ายทิ้ง
elif a[mid] < target:
low = mid + 1ใหญ่เกินไป ให้ไปทางซ้าย
หาก a[mid] มากกว่าเป้าหมาย ให้ค้นหาในครึ่งซ้าย เลื่อน high ไปที่ mid - 1 เพื่อไม่ต้องตรวจสอบ mid ซ้ำอีก
else:
high = mid - 1เงื่อนไขของลูป
ทำงานต่อไป ขณะที่ low น้อยกว่าหรือเท่ากับ high เมื่อทั้งสองข้ามกัน ช่วงจะว่างเปล่าและไม่มีเป้าหมายอยู่
while low <= high:
mid = low + (high - low) // 2รายงานว่าไม่พบ
หากลูปจบลงโดยไม่พบค่าที่ตรงกัน แสดงว่าไม่มีค่านั้นอยู่ ตามธรรมเนียมให้ คืนค่า -1 เพื่อให้ผู้เรียกแยกความสำเร็จจากความล้มเหลวได้
return -1 # target not in listกับดักความคลาดเคลื่อนทีละหนึ่ง
ข้อผิดพลาดคลาสสิกคือการลืม +1 หรือ -1 เมื่อเลื่อนตัวชี้ หากข้ามขั้นตอนนี้ mid จะถูกตรวจสอบซ้ำตลอดไปและทำให้เกิดลูปไม่รู้จบ
low = mid + 1 # not low = midใช้ไลบรารีเมื่อทำได้
สำหรับการทดสอบการมีสมาชิกแบบทั่วไป โมดูล bisect ของ Python มีการค้นหาที่ปราศจากข้อผิดพลาดอยู่แล้ว ให้เขียนลูปเองเฉพาะเมื่อต้องใช้ตรรกะแบบกำหนดเอง
import bisect
i = bisect.bisect_left(a, target)ตรวจสอบอย่างรวดเร็ว
ลองคิดดูว่าอะไรทำให้ลูปทำงานได้อย่างถูกต้อง
สรุปทบทวน: ค้นหาโดยไม่มีข้อผิดพลาด
ตอนนี้คุณสามารถกำหนด low และ high คำนวณ mid อย่างปลอดภัย ลดช่วงด้านที่ถูกต้อง และหลีกเลี่ยงกับดักความคลาดเคลื่อนทีละหนึ่งได้แล้ว การค้นหาแบบลอการิทึมอยู่ในมือคุณแล้ว 🎯
คำถามที่พบบ่อย
บทเรียน “การค้นหาแบบทวิภาคคลาสสิกที่ไร้บั๊ก” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “การค้นหาแบบทวิภาคคลาสสิกที่ไร้บั๊ก” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “การค้นหาแบบทวิภาคคลาสสิกที่ไร้บั๊ก”
กำหนดลูป low, high และ mid ให้ถูกต้อง คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน
บทเรียน “การค้นหาแบบทวิภาคคลาสสิกที่ไร้บั๊ก” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- การค้นหาแบบทวิภาคคลาสสิกที่ไร้บั๊ก
- bisect_left และ bisect_right
- True แรก: การค้นหาแบบทวิภาคด้วยภาคแสดง
- การค้นหาแบบทวิภาคบนคำตอบ