True แรก: การค้นหาแบบทวิภาคด้วยภาคแสดง
ค้นหาขอบเขตใช่/ไม่ใช่แบบโมโนโทน
True แรก: การค้นหาแบบทวิภาคด้วยภาคแสดง เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
ค้นหาขอบเขตจริงหรือเท็จ
ปัญหาหลายอย่างซ่อน เงื่อนไขแบบโมโนโทน ไว้ ซึ่งมีค่าเท็จต่อเนื่อง แล้วจึงเป็นค่าจริงตลอดไป การค้นหาแบบไบนารีสามารถหาค่าจริงตัวแรกได้โดยไม่ต้องมีอาร์เรย์ที่เรียงลำดับ
# FFFFTTTT -> find first Tความหมายของโมโนโทน
เงื่อนไขหนึ่งจะเป็น โมโนโทน เมื่อเปลี่ยนเป็นจริงแล้วจะยังคงเป็นจริงต่อไป คุณสมบัติเพียงข้อเดียวนี้ทำให้คุณค้นหาขอบเขตแบบไบนารีได้
def ok(x):
return x * x >= targetกำหนดช่วงของคำตอบ
เลือกช่วงที่แน่ใจว่าครอบคลุมขอบเขต ตั้ง low เป็นตัวเลือกที่เล็กที่สุด และ high เป็นค่าที่แน่ใจว่า ok เป็นจริง
low, high = 0, 10**9ทดสอบค่าตรงกลาง
รับค่า mid แล้วเรียกใช้ ok(mid) ผลลัพธ์บูลีนจะบอกว่าควรเก็บครึ่งใดไว้ เช่นเดียวกับการเปรียบเทียบค่าในการค้นหาแบบไบนารีทั่วไป
mid = (low + high) // 2
if ok(mid):
...จริงหมายความว่าอาจเล็กกว่านี้ได้
หาก ok(mid) เป็นจริง mid ก็เป็นคำตอบที่ใช้ได้ แต่อาจมีค่าที่เล็กกว่านี้ซึ่งใช้ได้เช่นกัน ให้เก็บ mid ไว้โดยกำหนด high = mid ไม่ใช่ mid - 1
if ok(mid):
high = midเท็จหมายความว่าต้องสูงขึ้น
หาก ok(mid) เป็นเท็จ ขอบเขตจะอยู่เหนือ mid ให้ตัด mid และทุกค่าด้านล่างทิ้งด้วย low = mid + 1
else:
low = mid + 1วนลูปขณะที่ Low ยังต่ำกว่า High
ใช้ while low < high ไม่ใช่เงื่อนไขน้อยกว่าหรือเท่ากับ ตัวชี้ทั้งสองจะเคลื่อนเข้าหาดัชนีจริงตัวแรก แล้วลูปจะหยุด
while low < high:
mid = (low + high) // 2คำตอบคือ Low
เมื่อลูปจบ low จะเท่ากับ high และทั้งคู่จะชี้ไปยังค่า จริงตัวแรก ให้คืนค่า low เป็นขอบเขตที่คุณกำลังค้นหา
return low # first x where ok(x)เหตุผลที่ high = mid ใช้ได้
เนื่องจาก mid อาจเป็นคำตอบ คุณจึง ห้ามข้ามมัน การใช้ high = mid จะเก็บ mid ไว้ในช่วงพร้อมกับทำให้ช่วงเล็กลง จึงรับประกันว่าการค้นหาจะคืบหน้า
high = mid # mid stays a candidateตัวอย่างรากที่สองจำนวนเต็ม
หาค่า x ที่มากที่สุดซึ่ง x*x ไม่เกิน n โดยค้นหา ค่าจริงตัวแรกของ x*x > n แล้วถอยกลับหนึ่งขั้น รูปแบบนี้นำกลับมาใช้ซ้ำได้
def ok(x):
return x * x > n
# answer is found_index - 1แม่แบบเดียว แก้ได้หลายปัญหา
แม่แบบ ค่าจริงตัวแรกนี้แก้ปัญหาได้มากมาย เช่น ค่าต่ำสุดที่เป็นไปได้ ดัชนีซ้ายสุด และความจุที่น้อยที่สุด เรียนรู้ครั้งเดียวแล้วนำไปใช้ได้ทุกที่
# low<high, ok->high=mid, else low=mid+1ตรวจสอบอย่างรวดเร็ว
ระบุขั้นตอนที่ทำให้ตัวเลือกคำตอบยังคงอยู่
สรุปทบทวน: พบค่าจริงตัวแรก
ตอนนี้คุณสามารถเปลี่ยนปัญหาให้เป็น เงื่อนไขแบบโมโนโทน และค้นหาขอบเขตแบบไบนารีได้แล้ว high = mid พร้อมกับ while low < high คือรูปแบบที่ปลอดภัย 🧭
คำถามที่พบบ่อย
บทเรียน “True แรก: การค้นหาแบบทวิภาคด้วยภาคแสดง” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “True แรก: การค้นหาแบบทวิภาคด้วยภาคแสดง” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “True แรก: การค้นหาแบบทวิภาคด้วยภาคแสดง”
ค้นหาขอบเขตใช่/ไม่ใช่แบบโมโนโทน คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน
บทเรียน “True แรก: การค้นหาแบบทวิภาคด้วยภาคแสดง” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- การค้นหาแบบทวิภาคคลาสสิกที่ไร้บั๊ก
- bisect_left และ bisect_right
- True แรก: การค้นหาแบบทวิภาคด้วยภาคแสดง
- การค้นหาแบบทวิภาคบนคำตอบ