binsearch z "wyłączaniem" niektórych elementów

Witam!

Szukam modyfikacji do binsearcha, która pozwoliłaby mi "wyłączać" niektóre elementy ciągu tak aby binsearch ich nie dotyczył. Powiedzmy, że mam jakąś posortowaną macierz o N elementach. Potrafię w czasie stałym powiedzieć, czy dany element jest "wyłączony" , czy nie. Chciałbym teraz wyszukać w tej tablicy za pomocą binsearcha element spełniający jakieś moje kryteria nie uwzględniając przy tym "wyłączonych" elementów. Takich operacji chciałbym móc wykonać dowolnie dużo i za każdym razem chcę móc wyłączać dowolne elementy ciągu. Oczywiście nie mogę sobie tak po prostu za każdym razem usuwać tych elementów bo trwałoby to liniowo długo, a to musi koniecznie działać w n log n . Czy to w ogóle jest możliwe?

Co to znaczy "nie uwzględniając tym wyłączonych elementów"? Jak funkcja znajdzie jeden z nich, to ma zwrócić, że nie znaleziono?

tak

O(nlogn) nie będzie, bo macierz jest n * n. Teraz, skąd binary search ma wiedzieć, których elementów nie zwracać? Nie prościej, nieszukać wyłączonych elementów, skoro Wiesz jakie to są?

Jeśli wyłączanie polega na tym, że dopiero podczas porównywania elementu (w sensie: sprawdzania warunku wyszukiwania na wytypowanym elemencie) dowiadujemy się, że jest wyłączony no to sorry - pesymistyczny czas wyszukiwania będzie liniowy, bo w pesymistycznym przypadku wszystkie elementy są wyłączone i trzeba sprawdzać wszystkie elementy, by się o tym przekonać. W takim przypadku po prostu najpierw zrób binsearcha tak, jakby wszystkie elementy były włączone, a potem (jeśli początkowo trafiłeś na wyłączony element) liniowo skanuj w odpowiednim kierunku, aż znajdziesz włączony element.

Natomiast jeśli wyłączanie jest osobnym krokiem od szukania to po prostu użyj posortowanego zbioru (lub dwóch - jeden z włączonymi elementami, a drugi z wyłączonymi). Posortowane zbiory są zwykle oparte o zrównoważone drzewa poszukiwań binarnych, gdzie wyszukiwanie, dodawanie i usuwanie elementów zajmują czasy logarytmiczne.

Może kopiuj elementy nie wyłączone do nowej struktury, w której zrobisz binarysearch, Jeśli x to procent nie wyłączonych elementów to wtedy złożoność wszystkich operacji wynosi N + Nxlog(N*x). Już przy x=94% liczba operacji jest zbliżona do czasu na wszystkich N elementach, Jeśli ten procent wyłączonych jest mniejszych niż 6% to myślę, że szkoda zachodu.