Hej, mam uporządkowaną tablicę typu int. Chcę wyszukać daną wartość i podać liczbę jej wystąpień. Napisałem algorytm zwykłego wyszukiwania binarnego i potem na piechotę sprawdzałem wartości z lewej i z prawej strony znalezionego przeze mnie indeksu by określić jaka jest ich ogólna liczba. Niestety wykładowca stwierdził że w pesymistycznym przypadku tablica będzie zawierać dokładnie takie same elementy i w efekcie mój algorytm może mieć złożoność liniową co jest niedozwolone. Zadanie należy rozwiązać tak by znaleźć indeks pierwszego i ostatniego wystąpienia danego elementu w tablicy, odjąć indeks ostatni od pierwszego i w ten sposób uzyskać ilość duplikatów. Jednak mnie się wydaje że aby znaleźć pierwsze wystąpienie elementu np. 9 to trzeba najpierw znaleźć ostatnie wystąpienie elementu 8, czyli znów algorytm wyszukiwania binarnego i przesuwanie się w prawo aż do liczby 9, a co jeśli 8 nie ma w tablicy? Szukam 7, jak 7 nie ma to 6, jak 6 nie ma to 5 i tak aż do najmniejszego możliwego inta? Może ja czegoś w tym algorytmie nie ogarniam, proszę o pomoc. Pozdrawiam
0
0
W normalnym wyszukiwaniu binarnym rozpatrujesz trzy warianty: tb[i]<x, tb[i]=x, tb[i]>x
W tym przypadku musisz:
- najpierw wyszukać rozpatrując dwa warianty:
tb[i]<=x,tb[i]>x - potem wyszukać rozpatrując dwa warianty:
tb[i]<x,tb[i]>=x