bisect_left และ bisect_right
ค้นหาจุดแทรกในลิสต์ที่เรียงแล้ว
bisect_left และ bisect_right เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
ค้นหาโดยไม่ต้องเขียนโค้ดซ้ำซ้อน
โมดูล bisect ของ Python มีการค้นหาแบบไบนารีที่ผ่านการทดสอบแล้วสำหรับรายการที่เรียงลำดับ ไม่ต้องเขียนลูปเอง จึงไม่มีข้อผิดพลาดความคลาดเคลื่อนทีละหนึ่งให้แก้ไข
import bisectจุดแทรก ไม่ใช่ค่าบูลีน
แทนที่จะคืนค่าจริงหรือเท็จ bisect จะคืนค่า ดัชนี ที่ควรแทรกค่าเพื่อให้รายการยังเรียงลำดับอยู่ ดัชนีนั้นคือประโยชน์สำคัญของมัน
a = [1, 3, 3, 3, 7]bisect_left เอนเอียงไปทางซ้าย
bisect_left คืนตำแหน่งแรกที่สามารถวางค่าได้ สำหรับค่าซ้ำ ตำแหน่งนี้จะอยู่ก่อนรายการที่เท่ากันทั้งหมดและไม่อยู่หลังรายการเหล่านั้น
bisect.bisect_left(a, 3) # 1bisect_right เอนเอียงไปทางขวา
bisect_right คืนตำแหน่งถัดจากสมาชิกตัวสุดท้ายที่เท่ากันพอดี สำหรับค่าซ้ำ ตำแหน่งนี้จะอยู่หลังค่าที่ตรงกันทั้งหมด
bisect.bisect_right(a, 3) # 4นับสมาชิกที่เท่ากัน
ลบค่าทั้งสองเพื่อ นับค่าซ้ำ ของค่าใดค่าหนึ่งใน O(log n) โดย right ลบด้วย left จะให้จำนวนครั้งที่ค่านั้นปรากฏพอดี
lo = bisect.bisect_left(a, 3)
hi = bisect.bisect_right(a, 3)
print(hi - lo) # 3ค่านั้นมีอยู่หรือไม่
ในการตรวจสอบสมาชิก ให้รับค่า i จาก bisect_left แล้วตรวจสอบว่า a[i] เท่ากับเป้าหมาย โดยต้องตรวจสอบก่อนว่า i ไม่ได้ถึงความยาวของรายการ
i = bisect.bisect_left(a, x)
found = i < len(a) and a[i] == xสมาชิกตัวแรกที่ไม่น้อยกว่า X
bisect_left ยังใช้ค้นหาสมาชิกตัวแรกที่มากกว่าหรือเท่ากับ x ได้ ดัชนีนั้นชี้ตรงไปยังคำตอบขอบเขตล่าง
i = bisect.bisect_left(a, x) # first >= xสมาชิกตัวแรกที่มากกว่าอย่างเคร่งครัด
ต้องการสมาชิกตัวแรกที่มากกว่า x อย่างเคร่งครัดหรือไม่ bisect_right จะให้ดัชนีนั้นโดยตรง ซึ่งเป็นขอบเขตบนในอีกด้านหนึ่ง
i = bisect.bisect_right(a, x) # first > xแทรกโดยยังคงลำดับไว้
insort ค้นหาตำแหน่งและแทรกค่าในการเรียกครั้งเดียว โดยรักษาลำดับของรายการไว้ เหมาะสำหรับสร้างโครงสร้างที่เรียงลำดับแบบทันทีระหว่างประมวลผล
bisect.insort(a, 5) # a stays sortedค้นหาภายในหน้าต่าง
อาร์กิวเมนต์ lo และ hi ซึ่งเป็นทางเลือก จะจำกัดการค้นหาไว้ในส่วนย่อย วิธีนี้หลีกเลี่ยงการคัดลอกข้อมูลเมื่อคุณสนใจเพียงช่วงย่อย
bisect.bisect_left(a, x, 2, 5)ใช้รายการช่วยเก็บคีย์
bisect เปรียบเทียบสมาชิกทั้งตัว ดังนั้นหากต้องการค้นหาตาม ฟิลด์ ให้สร้างรายการคู่ขนานที่มีเฉพาะคีย์เหล่านั้น แล้วใช้ bisect กับรายการนั้นแทน
keys = [p[0] for p in pairs]
i = bisect.bisect_left(keys, target)ตรวจสอบอย่างรวดเร็ว
วิเคราะห์ค่าซ้ำและจุดแทรก
สรุปทบทวน: เชี่ยวชาญ Bisect
ตอนนี้คุณสามารถค้นหา จุดแทรก นับค่าซ้ำ และหาขอบเขตล่างกับขอบเขตบนได้ในเวลาแบบลอการิทึม ให้เลือกใช้ bisect ก่อนเขียนลูป ✨
คำถามที่พบบ่อย
บทเรียน “bisect_left และ bisect_right” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “bisect_left และ bisect_right” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “bisect_left และ bisect_right”
ค้นหาจุดแทรกในลิสต์ที่เรียงแล้ว คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน
บทเรียน “bisect_left และ bisect_right” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- การค้นหาแบบทวิภาคคลาสสิกที่ไร้บั๊ก
- bisect_left และ bisect_right
- True แรก: การค้นหาแบบทวิภาคด้วยภาคแสดง
- การค้นหาแบบทวิภาคบนคำตอบ