Binary Search (bisect) ใน Python

ที่นี่เราจะดู bisect ใน Python ฟังก์ชัน bisect ใช้สำหรับ Binary Search (การค้นหาแบบทวิภาค) เทคนิค binary search ใช้หาองค์ประกอบในรายการที่จัดเรียงแล้ว bisect เป็นฟังก์ชันของไลบรารี

เราจะดู 3 งานที่แตกต่างกันโดยใช้ bisect ใน Python

หาความปรากฏครั้งแรกขององค์ประกอบ

ฟังก์ชัน bisect.bisect_left(a, x, lo=0, hi=len(a)) ใช้คืนค่าจุดแทรกซ้ายสุดของ x ในรายการที่จัดเรียงแล้ว พารามิเตอร์สองตัวสุดท้ายเป็นตัวเลือกในกรณีนี้ ใช้สำหรับค้นหาใน sublist

ตัวอย่าง

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 (key) ได้

ตัวอย่าง

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 ในรายการที่จัดเรียงแล้ว พารามิเตอร์สองตัวสุดท้ายเป็นตัวเลือก ใช้สำหรับค้นหาใน sublist

ตัวอย่าง

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