อัลกอริทึมแบบแบ่งครึ่งใช้เพื่อค้นหาตำแหน่งในรายการ ซึ่งสามารถแทรกข้อมูลเพื่อจัดเรียงรายการได้ Python มีโมดูลที่เรียกว่า bisect . เมื่อใช้โมดูลนี้ เราสามารถใช้อัลกอริทึมแบบแบ่งครึ่งได้
ในการใช้โมดูลนี้ เราควรนำเข้าโดยใช้ −
import bisect
มีการดำเนินการที่เกี่ยวข้องกับการแบ่งเป็นสองส่วน เหล่านี้คือ −
วิธี bisect.bisect(รายการ องค์ประกอบ เริ่มต้น สิ้นสุด)
วิธีนี้ใช้เพื่อค้นหาตำแหน่งในรายการที่เรียงลำดับ ซึ่งหมายเลขสามารถวางและรายการยังคงเรียงลำดับ หากมีองค์ประกอบอยู่แล้ว องค์ประกอบจะส่งคืนตำแหน่งที่ถูกต้องที่สุด ซึ่งสามารถแทรกตัวเลขได้
วิธีการ bisect.bisect_left(รายการ องค์ประกอบ เริ่มต้น สิ้นสุด)
วิธีนี้เหมือนกับวิธี bisect() ข้อแตกต่างเพียงอย่างเดียวคือ หากมีรายการอยู่แล้ว วิธีนี้จะคืนค่าตำแหน่งด้านซ้ายสุดเพื่อแทรกข้อมูล
วิธีการ bisect.bisect_right(รายการ องค์ประกอบ เริ่มต้น สิ้นสุด)
วิธีนี้เหมือนกับวิธี bisect() โดยสิ้นเชิง
วิธี bisect.insort(รายการ องค์ประกอบ เริ่มต้น สิ้นสุด)
วิธีนี้ใช้เพื่อรับรายการที่จัดเรียงหลังจากแทรกองค์ประกอบในตำแหน่งที่ถูกต้อง หากมีองค์ประกอบอยู่แล้ว องค์ประกอบจะแทรกที่ตำแหน่งขวาสุดเพื่อจัดเรียงรายการ
วิธี bisect.insort_left(รายการ องค์ประกอบ เริ่มต้น สิ้นสุด)
เมธอดนี้เหมือนกับวิธี insort() ข้อแตกต่างเพียงอย่างเดียวคือ หากมีองค์ประกอบอยู่แล้ว องค์ประกอบจะแทรกที่ตำแหน่งซ้ายสุดเพื่อจัดเรียงรายการ
วิธีการ bisect.insort_right(รายการ องค์ประกอบ เริ่มต้น สิ้นสุด)
เมธอดนี้เหมือนกับเมธอด insort()
โค้ดตัวอย่าง
import bisect
my_list = [11, 25, 36, 47, 56, 69, 69, 69, 78, 78, 91, 102, 120]
print('Correct Location to insert 53 is: ' + str(bisect.bisect(my_list, 53, 0, len(my_list))))
print('Correct right Location to insert 69 is: ' + str(bisect.bisect_right(my_list, 69, 0, len(my_list))))
print('Correct left Location to insert 69 is: ' + str(bisect.bisect_left(my_list, 69, 0, len(my_list))))
bisect.insort(my_list, 59, 0, len(my_list))
print(my_list)
bisect.insort_left(my_list, 78, 0, len(my_list))
print(my_list)
ผลลัพธ์
Correct Location to insert 53 is: 4 Correct right Location to insert 69 is: 8 Correct left Location to insert 69 is: 5 [11, 25, 36, 47, 56, 59, 69, 69, 69, 78, 78, 91, 102, 120] [11, 25, 36, 47, 56, 59, 69, 69, 69, 78, 78, 78, 91, 102, 120]
