T[1, . . . , n]
. Podaj algorytm (w pseudokodzie), działajacy w czasie \(\displaystyle{ O \left( \lg n \right)}\) i oparty na metodzie„dziel i zwyciezaj”, który sprawdza, czy istnieje indeks równy elementowi, czyli taki
indeks \(\displaystyle{ 1 < i < n}\), ze
T[i] = i
. Algorytm powinien zaczynac sie nastepujaco:
Kod: Zaznacz cały
Indeks(T[1, . . . , n])
1 . . .
T = [−7, 0, 2, 4, 7]
odpowiedz brzmi TAK, gdyz T[4] = 4
. Dla tablicy[2, 3, 4, 5]
odpowiedz brzmi NIE.Uzasadnij, dlaczego czas jego działania jest \(\displaystyle{ O \left( \lg n \right)}\).
Nie mam pojęcia jak się do tego zabrać, ktoś potrafi pomóc ?