Bisect-moduulin vaativuus¶

Moduuli bisect tarjoaa binäärihakuoperaatioita järjestetyille listoille.

Operaatiot¶

Operaatio	Aika	Tila	Huomiot
`bisect_left(a, x)`	O(log n)	O(1)	Etsii vasemmanpuoleisimman sijainnin
`bisect_right(a, x)`	O(log n)	O(1)	Etsii oikeanpuoleisimman sijainnin
`bisect(a, x)`	O(log n)	O(1)	Vaihtoehtoinen nimi funktiolle bisect_right
`insort_left(a, x)`	O(n)	O(1)	O(log n) haku + O(n) lisäys (siirtää alkioita paikallaan)
`insort_right(a, x)`	O(n)	O(1)	O(log n) haku + O(n) lisäys (siirtää alkioita paikallaan)
`insort(a, x)`	O(n)	O(1)	Vaihtoehtoinen nimi funktiolle insort_right

Tilavaativuus¶

Binäärihakuoperaatiot: O(1) lisätilaa
Lisäysoperaatiot: O(1) lisätilaa (siirtää alkioita olemassa olevan listan sisällä)

Toteutuksen yksityiskohdat¶

Binäärihaun takuu¶

import bisect

# Must be sorted!
sorted_list = [1, 3, 3, 3, 5, 7, 9]

# bisect_left: leftmost insertion point
pos = bisect.bisect_left(sorted_list, 3)  # pos = 1
# Insert here to keep list sorted (before all 3's)

# bisect_right: rightmost insertion point
pos = bisect.bisect_right(sorted_list, 3)  # pos = 4
# Insert here to keep list sorted (after all 3's)

Alkioiden etsiminen¶

import bisect

sorted_list = [1, 3, 5, 7, 9]

# Check if element exists
def exists(sorted_list, x):
    pos = bisect.bisect_left(sorted_list, x)
    return pos < len(sorted_list) and sorted_list[pos] == x

exists(sorted_list, 5)  # True - O(log n)
exists(sorted_list, 4)  # False - O(log n)

Yleiset käyttötapaukset¶

Lisäys järjestystä säilyttäen¶

import bisect

sorted_list = [1, 3, 5, 7]

# Insert while maintaining order - O(n) overall
# (O(log n) search + O(n) shift)
bisect.insort(sorted_list, 4)  # [1, 3, 4, 5, 7]

# Better for many insertions: use list, then sort
# Multiple inserts: O(n log n) with sort
# vs O(n²) with repeated insort

Välien etsiminen¶

import bisect

# Find all equal elements
sorted_list = [1, 3, 3, 3, 5, 7, 9]
target = 3

left = bisect.bisect_left(sorted_list, target)
right = bisect.bisect_right(sorted_list, target)

equals = sorted_list[left:right]  # All 3's - O(log n) search

Välin lisäyskohdan etsiminen¶

import bisect

# Find where range [a, b] fits in sorted list
sorted_list = [1, 5, 10, 15, 20]
target_range = (7, 12)

# Position to insert start of range
start_pos = bisect.bisect_right(sorted_list, target_range[0])

# Position to insert end of range
end_pos = bisect.bisect_left(sorted_list, target_range[1])

print(f"Insert range {target_range} at positions {start_pos}-{end_pos}")

Suorituskyvyn vertailu¶

Haku järjestetystä datasta¶

import bisect

data = sorted(range(1000000))

# Bad: Linear search - O(n)
found = 500000 in data  # Scans linearly

# Good: Binary search - O(log n)
pos = bisect.bisect_left(data, 500000)  # Much faster!
found = pos < len(data) and data[pos] == 500000

Järjestettyjen listojen ylläpito¶

import bisect

# Many insertions scenario
sorted_list = [1, 3, 5, 7, 9]

# Bad: Multiple insort - O(n²)
for item in [2, 4, 6, 8]:
    bisect.insort(sorted_list, item)  # O(n) each

# Better: Collect, sort once - O(n log n)
sorted_list.extend([2, 4, 6, 8])
sorted_list.sort()  # Single O(n log n) operation

Yksityiskohtaiset esimerkit¶

Arvosanavälit¶

import bisect

# Map scores to grades
grade_breaks = [60, 70, 80, 90]
grades = ['F', 'D', 'C', 'B', 'A']

def get_grade(score):
    i = bisect.bisect(grade_breaks, score)
    return grades[i]

print(get_grade(85))  # 'B' - O(log n)
print(get_grade(95))  # 'A' - O(log n)

Aikaleimahaku¶

import bisect
from datetime import datetime, timedelta

# Find events in a time range
events = [
    (datetime(2024, 1, 1, 10), 'event1'),
    (datetime(2024, 1, 1, 12), 'event2'),
    (datetime(2024, 1, 1, 15), 'event3'),
    (datetime(2024, 1, 1, 18), 'event4'),
]

timestamps = [e[0] for e in events]

# Find events after specific time
target = datetime(2024, 1, 1, 14)
idx = bisect.bisect_right(timestamps, target)
later_events = events[idx:]  # O(log n) search

print(later_events)  # Events at 3pm and 6pm

Edistynyt: omat avainfunktiot¶

import bisect
from bisect import bisect_right

# Custom objects - compare by second element
data = [('a', 1), ('b', 3), ('c', 5)]
keys = [x[1] for x in data]

# Find position for ('d', 4)
pos = bisect_right(keys, 4)
data.insert(pos, ('d', 4))

Tärkeitä huomioita¶

Vaatimus järjestetystä datasta

Syötelistan TÄYTYY olla järjestetty, jotta binäärihaku toimii oikein.

# Wrong: Data not sorted
unsorted = [3, 1, 4, 1, 5]
pos = bisect.bisect(unsorted, 2)  # Incorrect result!

Tasoitettu tehokkuus

Kun lisäyksiä on paljon:

Useita insort()-kutsuja: yhteensä O(n²)
Kerää ensin ja kutsu sort() kerran: yhteensä O(n log n)

Valitse käyttötapasi mukaan.