ขอบเขตล่างและขอบเขตบน

ขอบเขตล่างและขอบเขตบนคืออะไร

arr = [1, 2, 2, 2, 3, 5]
# lower bound of 2 => index 1 (first element >= 2)
# upper bound of 2 => index 4 (first element > 2)
# occurrences of 2 => upper - lower = 4 - 1 = 3
print('lower bound of 2:', 1)
print('upper bound of 2:', 4)
print('count of 2:', 4 - 1)

การนำขอบเขตล่างไปใช้งาน (bisect_left)

def bisect_left(arr, x):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < x:
            lo = mid + 1
        else:
            hi = mid      # arr[mid] >= x, so potential answer
    return lo             # lo == hi == insertion point

arr = [1, 2, 2, 2, 3, 5]
print(bisect_left(arr, 2))   # 1
print(bisect_left(arr, 0))   # 0 (before all)
print(bisect_left(arr, 6))   # 6 (after all)
print(bisect_left(arr, 3))   # 4

การนำขอบเขตบนไปใช้งาน (bisect_right)

def bisect_right(arr, x):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] <= x:
            lo = mid + 1  # arr[mid] <= x, so answer is strictly right
        else:
            hi = mid
    return lo

arr = [1, 2, 2, 2, 3, 5]
print(bisect_right(arr, 2))  # 4
print(bisect_right(arr, 0))  # 0
print(bisect_right(arr, 5))  # 6
print(bisect_right(arr, 4))  # 5

นับจำนวนครั้งที่ปรากฏด้วยขอบเขตทั้งสอง

import bisect

def count_occurrences(arr, target):
    left  = bisect.bisect_left(arr, target)
    right = bisect.bisect_right(arr, target)
    return right - left

arr = [1, 2, 2, 2, 3, 3, 5]
print(count_occurrences(arr, 2))  # 3
print(count_occurrences(arr, 3))  # 2
print(count_occurrences(arr, 4))  # 0
print(count_occurrences(arr, 1))  # 1

หาตำแหน่งแรกและตำแหน่งสุดท้ายของเป้าหมาย

import bisect

def search_range(nums, target):
    left = bisect.bisect_left(nums, target)
    if left == len(nums) or nums[left] != target:
        return [-1, -1]
    right = bisect.bisect_right(nums, target) - 1
    return [left, right]

print(search_range([5,7,7,8,8,10], 8))  # [3, 4]
print(search_range([5,7,7,8,8,10], 6))  # [-1, -1]
print(search_range([], 0))              # [-1, -1]

ตำแหน่งแทรก (LeetCode 35)

import bisect

def searchInsert(nums, target):
    return bisect.bisect_left(nums, target)

print(searchInsert([1,3,5,6], 5))  # 2 (exists at index 2)
print(searchInsert([1,3,5,6], 2))  # 1 (would insert between 1 and 3)
print(searchInsert([1,3,5,6], 7))  # 4 (would append at end)
print(searchInsert([1,3,5,6], 0))  # 0 (would prepend)

ความแตกต่างระหว่าง bisect_left กับ bisect_right

import bisect

arr = [1, 2, 2, 2, 3]

# Insert a new 2 before all existing 2s
print(bisect.bisect_left(arr, 2))   # 1

# Insert a new 2 after all existing 2s
print(bisect.bisect_right(arr, 2))  # 4

# For a value not in array, both give same insertion point
print(bisect.bisect_left(arr, 2.5))  # 4
print(bisect.bisect_right(arr, 2.5)) # 4

การใช้ขอบเขตกับการสอบถามความถี่ในช่วงของข้อมูลเรียงลำดับ

import bisect

def count_in_range(arr, lo, hi):
    '''Count elements in arr with lo <= val <= hi. arr must be sorted.'''
    left  = bisect.bisect_left(arr, lo)
    right = bisect.bisect_right(arr, hi)
    return right - left

arr = sorted([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])
print(arr)                          # [1,1,2,3,3,4,5,5,5,6,9]
print(count_in_range(arr, 3, 5))    # 6  (3,3,4,5,5,5)
print(count_in_range(arr, 1, 2))    # 3  (1,1,2)

การทำ binary search ด้วยคีย์แบบกำหนดเอง

# Binary search on a list of (score, name) tuples by score
def lower_bound_by_score(records, min_score):
    lo, hi = 0, len(records)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if records[mid][0] < min_score:
            lo = mid + 1
        else:
            hi = mid
    return lo

records = [(50, 'Alice'), (72, 'Bob'), (72, 'Carol'), (88, 'Dave'), (95, 'Eve')]
idx = lower_bound_by_score(records, 72)
print(idx)                      # 1 (first record with score >= 72)
print(records[idx:])            # [(72,'Bob'),(72,'Carol'),(88,'Dave'),(95,'Eve')]

ข้อผิดพลาดทั่วไปในการสัมภาษณ์เกี่ยวกับขอบเขต

import bisect

arr = [1, 3, 5, 7]
target = 4

# bisect_left returns 2 (insertion point for 4 between 3 and 5)
idx = bisect.bisect_left(arr, target)
print(idx)              # 2
# Validate: arr[2] is 5, not 4 => target absent
found = idx < len(arr) and arr[idx] == target
print('Found:', found)  # False

สรุป: ควรใช้ bisect_left หรือ bisect_right เมื่อใด

ตรวจสอบอย่างรวดเร็ว

สรุปบทเรียน