البحث الثنائي وثوابت الحدود

def lower_bound(values, target):
    lo, hi = 0, len(values)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

print(lower_bound([1, 3, 3, 8], 3))
print(lower_bound([1, 3, 3, 8], 9))
print(lower_bound([], 3))

1
4
0

تبدأ القيم المكررة 3 عند الفهرس 1. ويكون موضع إدراج الهدف 9 بعد العنصر الأخير، ويملك التسلسل الفارغ حد إدراج 0.

from bisect import bisect_left, bisect_right

def occurrences(values, target):
    return bisect_right(values, target) - bisect_left(values, target)

values = [1, 3, 3, 8]
print(occurrences(values, 3))
print(occurrences(values, 4))
position = bisect_left(values, 4)
print(position < len(values) and values[position] == 4)

2
0
False

موضع إدراج القيمة 4 صحيح بوصفه حدا، لكنه لا يعني وجود 4. ويعيد الحدان معا عدد ظهور صفريا بصورة صحيحة.