ที่นี่เราจะเห็นการแบ่งครึ่งใน Python bisect ใช้สำหรับการค้นหาแบบไบนารี เทคนิคการค้นหาแบบไบนารีใช้เพื่อค้นหาองค์ประกอบในรายการที่เรียงลำดับ แบ่งครึ่งเป็นหนึ่งฟังก์ชันห้องสมุด
เราจะเห็นงานที่แตกต่างกันสามงานโดยใช้ bisect ใน Python
ค้นหาการเกิดขึ้นครั้งแรกขององค์ประกอบ
bisect.bisect_left(a, x, lo =0, hi =len(a)) ฟังก์ชันนี้ใช้เพื่อส่งคืนจุดแทรกด้านซ้ายสุดของ x ในรายการที่จัดเรียง พารามิเตอร์สองตัวสุดท้ายเป็นทางเลือกในกรณีนี้ สองตัวนี้ใช้สำหรับค้นหาในรายการย่อย
ตัวอย่าง
from bisect import bisect_left
def BinSearch(a, x):
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
else:
return -1
a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(4)
pos = BinSearch(a, x)
if pos == -1:
print(x, "is absent")
else:
print("First occurrence of", x, "is at position", pos) ผลลัพธ์
First occurrence of 4 is at position 2
ค้นหาค่าที่มากที่สุดซึ่งน้อยกว่า x
เมื่อใช้ตัวเลือก bisect_left เราจะได้รับค่าที่มากกว่า ซึ่งน้อยกว่า x (คีย์)
ตัวอย่าง
from bisect import bisect_left
def BinSearch(a, x):
i = bisect_left(a, x)
if i :
return i-1
else:
return -1
a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(8)
pos = BinSearch(a, x)
if pos == -1:
print(x, "is absent")
else:
print("Larger value, smaller than", x, "is at position", pos) ผลลัพธ์
Larger value, smaller than 8 is at position 4
ค้นหาตำแหน่งที่ถูกต้องที่สุดของ x
bisect.bisect_right(a, x, lo =0, hi =len(a)) ฟังก์ชันนี้ใช้เพื่อส่งคืนจุดแทรกที่ถูกต้องที่สุดของ x ในรายการที่จัดเรียง พารามิเตอร์สองตัวสุดท้ายเป็นทางเลือกในกรณีนี้ สองตัวนี้ใช้สำหรับค้นหาในรายการย่อย
ตัวอย่าง
from bisect import bisect_right
def BinSearch(a, x):
i = bisect_right(a, x)
if i != len(a) + 1 and a[i-1] == x:
return i-1
else:
return -1
a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(36)
pos = BinSearch(a, x)
if pos == -1:
print(x, "is absent")
else:
print("Right most occurrence of", x, "is at position", pos) ผลลัพธ์
Right most occurrence of 36 is at position 9
