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)  # O(log n), pos = 1
# Insert here to keep list sorted (before all 3's)

# bisect_right: rightmost insertion point
pos = bisect.bisect_right(sorted_list, 3)  # O(log n), pos = 4
# Insert here to keep list sorted (after all 3's)
# Both halve the search range each step, so a run of equal values costs no
# more than a unique one

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])  # O(log n)

# Position to insert end of range
end_pos = bisect.bisect_left(sorted_list, target_range[1])  # O(log n)
# Two independent searches: O(log n) total, not O(n)

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]  # O(n) - building the key list dominates

# Find position for ('d', 4)
pos = bisect_right(keys, 4)  # O(log n)
data.insert(pos, ('d', 4))  # O(n) - shifts the tail
# Rebuilding keys per search makes the whole thing O(n); keep it alongside
# data instead

Python 3.10 alkaen jokainen moduulin funktio ottaa key-argumentin, joka poistaa rinnakkaisen listan tarpeen:

import bisect

data = [('a', 1), ('b', 3), ('c', 5)]

# key runs once per probe, so no parallel list is needed
pos = bisect.bisect_right(data, 4, key=lambda item: item[1])  # O(log n) key calls
data.insert(pos, ('d', 4))  # O(n) - shifts the tail

Valinta riippuu siitä, kuinka moni haku jakaa samat avaimet: rinnakkainen lista maksaa O(n) kerran eikä yhtään kutsua hakua kohti, kun taas key ei maksa mitään etukäteen ja yhden kutsun jokaista koetinta kohti.

Tärkeitä huomioita¶

Vaatimus järjestetystä datasta

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

import bisect

# 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.

Versiohuomiot¶

Python 3.10+: key-parametri lisättiin jokaiseen moduulin funktioon