Dolna i górna granica
Zaimplementują Państwo od podstaw bisect_left i bisect_right, a następnie wykorzystają je do znalezienia pierwszej i ostatniej pozycji wartości docelowej.
Dolna i górna granica to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Czym są dolne i górne granice?
Dolna granica wartości docelowej w posortowanej tablicy to indeks pierwszego elementu większego lub równego wartości docelowej (często nazywany bisect_left). Górna granica to indeks pierwszego elementu ściśle większego od wartości docelowej (bisect_right). Razem wyznaczają przedział obejmujący każde wystąpienie wartości docelowej i umożliwiają wykonywanie zapytań o zakres w czasie O(log n).
Te dwie operacje stanowią podstawę wielu zadań rekrutacyjnych: zliczania wystąpień, znajdowania zakresu, wyznaczania pozycji wstawienia i wielu innych.
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)Implementacja dolnej granicy (bisect_left)
bisect_left(arr, x) zwraca najmniejszy indeks i taki, że arr[i] >= x, lub len(arr), jeśli wszystkie elementy są mniejsze. Implementacja używa wyłącznej granicy górnej: hi = len(arr), warunku pętli lo < hi oraz aktualizacji hi = mid, gdy arr[mid] >= x. Dzięki temu wynik zbiega do najmniejszej poprawnej pozycji.
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)) # 4Implementacja górnej granicy (bisect_right)
bisect_right(arr, x) zwraca najmniejszy indeks i taki, że arr[i] > x. Tylko jeden wiersz różni się od bisect_left: warunek zmienia się z arr[mid] < x na arr[mid] <= x. Gdy arr[mid] <= x, wynik znajduje się ściśle na prawo od mid, więc ustawiamy lo = mid + 1; w przeciwnym razie zawężamy zakres od prawej strony.
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)) # 5Zliczanie wystąpień przy użyciu obu granic
Aby zliczyć wystąpienia wartości docelowej w posortowanej tablicy w czasie O(log n), należy zastosować obie granice: count = bisect_right(arr, target) - bisect_left(arr, target). Jeśli count wynosi 0, wartość docelowa nie występuje w tablicy. Jest to znacznie szybsze niż liniowe przeszukiwanie i standardowe podejście do zapytań o częstotliwość w posortowanych danych.
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)) # 1Znajdowanie pierwszej i ostatniej pozycji wartości docelowej
LeetCode 34 „Znajdowanie pierwszej i ostatniej pozycji elementu w posortowanej tablicy” wymaga zwrócenia [first_idx, last_idx] w czasie O(log n). Pierwsza pozycja to bisect_left(arr, target) — ale tylko wtedy, gdy arr[result] == target. Ostatnia pozycja to bisect_right(arr, target) - 1. Jeśli którykolwiek z tych testów się nie powiedzie, należy zwrócić [-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]Pozycja wstawienia (LeetCode 35)
LeetCode 35 „Pozycja wstawienia” pyta, gdzie należy wstawić wartość docelową, aby zachować sortowanie tablicy. Jest to dokładnie bisect_left(arr, target). Jeśli wartość docelowa istnieje, bisect_left zwraca jej indeks. Jeśli nie istnieje, bisect_left zwraca indeks, pod którym należałoby ją wstawić. Nie trzeba stosować żadnych wyjątków — ta sama funkcja obsługuje oba przypadki.
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)Różnica między bisect_left a bisect_right
Gdy nie ma duplikatów, bisect_left i bisect_right zwracają ten sam indeks. Różnica ma znaczenie tylko wtedy, gdy wartość docelowa występuje wielokrotnie. bisect_left wskazuje pierwszą kopię; bisect_right wskazuje pozycję tuż za ostatnią kopią. Należy zawsze wybrać funkcję zależnie od tego, czy wartość ma zostać wstawiona przed istniejącymi kopiami (lewa granica), czy za nimi (prawa granica).
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)) # 4Zastosowanie granic w zapytaniach o częstotliwość dla posortowanych danych
Jeśli trzeba wydajnie obsługiwać wiele zapytań o częstotliwość elementów w zakresach posortowanej tablicy, należy jednorazowo przygotować posortowaną tablicę i używać bisect dla każdego zapytania. Każde zapytanie pozwala ustalić, „ile elementów znajduje się w [lo, hi]?”, w czasie O(log n) zamiast O(n). Ten schemat pojawia się w zadaniach dotyczących zliczania elementów należących do określonego zakresu wartości po posortowaniu.
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)Niestandardowe wyszukiwanie binarne z kluczem
Czasami kluczem wyszukiwania nie jest sama przechowywana wartość, lecz wartość wynikająca z określonej właściwości. Moduł Pythona bisect nie obsługuje bezpośrednio funkcji klucza, ale można ręcznie wykonać wyszukiwanie binarne, stosując klucz wewnątrz pętli. Ten schemat pojawia się podczas wyszukiwania na liście obiektów według jednego z ich atrybutów.
# 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')]Najczęstsze błędy na rozmowie technicznej związane z granicami
Najczęstszym błędem jest pominięcie sprawdzenia po wywołaniu bisect_left. Funkcja zawsze zwraca poprawny indeks wstawienia, ale nie gwarantuje, że element pod tym indeksem jest równy wartości docelowej. Przed uznaniem, że wartość docelowa została znaleziona, należy zawsze sprawdzić arr[result] == target.
Drugim błędem jest użycie bisect_right, gdy potrzebne jest pierwsze wystąpienie — bisect_right zwraca pozycję tuż za ostatnim wystąpieniem, więc odjęcie 1 daje ostatnie wystąpienie, a nie pierwsze.
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) # FalsePodsumowanie: kiedy używać bisect_left, a kiedy bisect_right
Należy użyć bisect_left, gdy potrzebne jest: pierwsze wystąpienie target, punkt wstawienia przesuwający istniejące kopie w prawo lub sprawdzenie, czy target istnieje. Należy użyć bisect_right, gdy potrzebne jest: wskazanie pozycji tuż za ostatnim wystąpieniem, punkt wstawienia za wszystkimi istniejącymi kopiami lub liczba elementów <= target (jest ona równa bisect_right(arr, target)).
Obie funkcje działają w czasie O(log n) i należą do standardowej biblioteki Pythona, więc można je bezpośrednio zaimportować i użyć, chyba że osoba prowadząca rozmowę poprosi o implementację od podstaw.
Szybki test
Sprawdź swoją znajomość zagadnień Data Structures & Algorithms — Coding Interview Prep omawianych w tej lekcji.
Podsumowanie lekcji
W tej lekcji poznali Państwo następujące zasady: bisect_left znajduje pierwszy element >= target, bisect_right znajduje pierwszy element > target (pozycję tuż za ostatnim wystąpieniem), a różnica między nimi daje liczbę wystąpień w czasie O(log n). W następnej części omówimy wyszukiwanie binarne w przestrzeni odpowiedzi, gdzie przestrzenią wyszukiwania jest zakres możliwych odpowiedzi, a nie indeks tablicy.
Często zadawane pytania
Czy lekcja „Dolna i górna granica” jest bezpłatna?
Tak — pełny tekst „Dolna i górna granica” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Dolna i górna granica”?
Zaimplementują Państwo od podstaw bisect_left i bisect_right, a następnie wykorzystają je do znalezienia pierwszej i ostatniej pozycji wartości docelowej. Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „Dolna i górna granica”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Klasyczne wyszukiwanie binarne: lewo, prawo, środek
- Wyszukiwanie binarne w tablicach obróconych i nieposortowanych
- Dolna i górna granica
- Wyszukiwanie binarne w przestrzeni odpowiedzi