Coding Interview Prep · บทเรียน

การค้นหาแบบทวิภาคบนคำตอบ

เดาผลลัพธ์และตรวจสอบความเป็นไปได้

บทเรียน 4 จาก 413 ขั้นตอน

การค้นหาแบบทวิภาคบนคำตอบ เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน

เดาแล้วตรวจสอบ

บางครั้งคุณคำนวณคำตอบโดยตรงไม่ได้ แต่สามารถ ตรวจสอบค่าที่เดาได้ การค้นหาคำตอบแบบไบนารีจะเปลี่ยนการหาค่าที่เหมาะที่สุดซึ่งยาก ให้กลายเป็นการตรวจสอบที่ง่าย

# guess X, ask: is X feasible?

คุณสมบัติมหัศจรรย์

วิธีนี้ใช้ได้เมื่อความเป็นไปได้มีลักษณะ โมโนโทน กล่าวคือ หากค่าหนึ่งใช้ได้ ค่าที่มากกว่าทั้งหมดหรือค่าที่น้อยกว่าทั้งหมดก็ใช้ได้เช่นกัน ลำดับนั้นคือสิ่งที่คุณกำลังค้นหา

# feasible(X) true => feasible(X+1) true

กำหนดขอบเขตช่วงคำตอบ

ระบุคำตอบที่เป็นไปได้ค่าต่ำสุดและค่าสูงสุดเป็น low และ high สำหรับความจุขั้นต่ำ low คือขนาดของสิ่งของหนึ่งชิ้น และ high คือผลรวมทั้งหมด

low, high = max(weights), sum(weights)

เขียนการตรวจสอบความเป็นไปได้

หัวใจของวิธีนี้คือ ฟังก์ชัน can(X) ที่คืนค่าเป็นจริงหากสามารถทำให้คำตอบ X เกิดขึ้นได้ โดยทั่วไปฟังก์ชันนี้ทำงานในเวลาเชิงเส้น

def can(cap):
    # simulate and return True/False
    ...

ตัวอย่าง: จัดส่งภายใน D วัน

เมื่อกำหนดความจุต่อวัน cap ให้เติมสิ่งของลงในแต่ละวันแบบโลภและนับจำนวนวัน can(cap) จะเป็นจริงเมื่อจำนวนวันไม่เกินขีดจำกัด D

def can(cap):
    days, load = 1, 0
    for w in weights:
        if load + w > cap:
            days += 1; load = 0
        load += w
    return days <= D

ค้นหาความจุขั้นต่ำ

คุณต้องการค่า cap ที่น้อยที่สุดและผ่านการตรวจสอบ นี่คือการค้นหา ค่าจริงตัวแรกบนช่วงความจุ ดังนั้นให้นำแม่แบบ high = mid กลับมาใช้

while low < high:
    mid = (low + high) // 2

เก็บครึ่งที่เป็นไปได้ไว้

หาก can(mid) เป็นจริง ความจุที่น้อยกว่านี้อาจยังใช้ได้ จึงกำหนด high = mid มิฉะนั้นให้เพิ่มขอบเขตล่างด้วย low = mid + 1

if can(mid):
    high = mid
else:
    low = mid + 1

คำนึงถึงงบเวลา

ค่าใช้จ่ายทั้งหมดคือ O(จำนวนครั้งตรวจสอบ x log ของช่วง) การตรวจสอบเชิงเส้นบนช่วงที่กว้างถึงหนึ่งพันล้านใช้การตรวจสอบเพียงประมาณ 30 ครั้ง จึงเร็วพอสำหรับขีดจำกัดที่เข้มงวด

# log2(1e9) is about 30 iterations

หาค่าสูงสุดแทนค่าต่ำสุด

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

if can(mid):
    low = mid
else:
    high = mid - 1

คำตอบที่เป็นค่าจริง

สำหรับคำตอบแบบทศนิยม ให้ทำลูปตามจำนวนรอบคงที่ เช่น 100 รอบ แทนการใช้ mid แบบจำนวนเต็ม แต่ละรอบจะลดช่วงลงครึ่งหนึ่งและได้ ความแม่นยำสูงมากอย่างรวดเร็ว

for _ in range(100):
    mid = (low + high) / 2

มองหารูปแบบ

วลีอย่าง ค่าต่ำสุดของค่าสูงสุด ค่าสูงสุดของค่าต่ำสุด หรือ k ที่น้อยที่สุดซึ่งใช้ได้ ล้วนเป็น สัญญาณให้ค้นหาคำตอบแบบไบนารี ฝึกสังเกตวลีเหล่านี้

# 'minimize the maximum' => search answer

ตรวจสอบอย่างรวดเร็ว

ตัดสินใจว่าควรใช้การค้นหาคำตอบแบบไบนารีเมื่อใด

ตอบคำถามในบทเรียนแบบโต้ตอบ

สรุปทบทวน: ค้นหาคำตอบ

ตอนนี้คุณสามารถกำหนดขอบเขตคำตอบ เขียน การตรวจสอบความเป็นไปได้ และค้นหาแบบไบนารีเพื่อหาค่าต่ำสุดหรือค่าสูงสุดได้แล้ว ปัญหายาก ๆ กลายเป็นการเดาแล้วตรวจสอบ 🏆

เริ่มต้นได้ฟรี

เรียนรู้ Coding Interview Prep ด้วย AI tutor — ฟรี

เขียนและเรียกใช้โค้ดจริงในเบราว์เซอร์ของคุณ รับความช่วยเหลือทันทีจาก AI tutor 24/7 และเรียนรู้ต่อจากที่คุณหยุดบนเว็บหรือในแอป

คอร์ส: 90
บทเรียน: 360

เริ่มเรียนฟรี ดูหลักสูตรเต็ม

คำถามที่พบบ่อย

บทเรียน “การค้นหาแบบทวิภาคบนคำตอบ” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “การค้นหาแบบทวิภาคบนคำตอบ” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “การค้นหาแบบทวิภาคบนคำตอบ”

เดาผลลัพธ์และตรวจสอบความเป็นไปได้ คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน

บทเรียน “การค้นหาแบบทวิภาคบนคำตอบ” ใช้เวลานานแค่ไหน

บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย

ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม

ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

← กลับไปที่ Coding Interview Prep