Wyszukiwanie binarne

Mamy dany posortowany ciąg różnych liczb całkowitych w A[1, . . . , n].

Mam napisać algorytm, który:
a) opiera się na metodzie „dziel i zwyciężaj”
b) działa w czasie O(lg n)
c) sprawdza, czy istnieje taki indeks 1<=j<=n, że A[j]=j

Do tego był dołączony przykład:

Dla A= [−7, 0, 2, 4, 7] --> TAK, bo A[4] = 4.
Dla A=[2, 3, 4, 5] --> NIE.

Nie pisze, co to może być, myślę, że to może być wyszukiwanie binarne, bo zgadzają się z tym podpunkty a, b i c. Dobrze myślę?

A co do przykładu, to rozumiem, że musi się zgadzać element oraz indeks?

Którego słowa w punkcie (c) nie rozumiesz?

Zastanawiam się, czy to zadanie ma coś wspólnego z wyszukiwaniem binarnym?

Wyszukiwanie binarne służy do znalezienia elementu, a w tym zadaniu mamy znaleźć taki sam indeks co element? Skoro A[j]=j.

Nie wiem, czy dobrze myślę, czy może źle.

Pewnie chodzi o to, że docelowy algorytm jest bardzo podobny do wyszukiwania binarnego. O ile dobrze sobie ten algo wyobrażam to chyba jedyna różnica jest w porównywaniu: zamiast porównywać A[j] z szukanym elementem porównuje się go z j.

Wykonujesz: A[j]=A[j]-j; dla każdego j
Po czym szukasz zera.
UWAGA!! To tylko dla zrozumienia tak robisz (w myślach), realnie to robisz tak jak napisał @Wibowit.

Dzięki za wyjaśnienie. A co z tym "dziel i zwyciężaj"? Czyli muszę dodać nową zmiennę np. m, która będzie wykonywała metodę "dziel"?

lenek32 napisał(a):

Dzięki za wyjaśnienie. A co z tym "dziel i zwyciężaj"? Czyli muszę dodać nową zmiennę np. m, która będzie wykonywała metodę "dziel"?

Ale po co? Wyszukiwanie binarne to algorytm typu "dziel i zwyciężaj" i o to tu chodzi.

Hmm, chyba jednak mam problem z napisaniem tego algorytmu, bo nie mam pomysłu, jak to zrobić.

Algorytm wyszukiwania binarnego wygląda tak:

WB(A[1..n],e)
l<--1
r<--n
while l<=r
   do m<--(l+r)/2    //(l+r)/2 jako podłoga
if e=A[m]
   then return m
if e<A[m]
   then r<--m-1
   else l<--m+1
return 0

Na razie napisałem tak:

ALGORYTM(A[1..n],e)
for j<--1 to n
    do l<--1
       r<--n
        while l<=r
           do m<--(l+r)/2              //(l+r)/2 jako podłoga
if e=A[m] and j=A[j]
   then return j
if e<A[m]
   then r<--m-1
   else l<--m+1
return 0

Wiem, że jest źle, ale na razie spróbowałem go napisać. Prosiłbym o wskazówki.

Bo jak podamy cyfrę, którą chcemy poszukać jako element i indeks, np. 4 to pytanie, które to "e" czy "j"? Musi być jedna zmienna, czyli "j", ale co z "e"?

WB(A[1..n])
a <- 1
b <- n+1
while a<b
   m <- (a+b)/2
   if A[m]=m then return m
   if A[m]<m
      then a <- m+1
      else b <- m
return 0

WB(A[1..n],a,b)
m <- (a+b)/2
if A[m]<m then return WB(A,m+1,b)
if A[m]>m then return WB(A,a,m)
return return m

Nie podajesz e. Zamiast porówywać e z A[m] porównuj m z A[m]. To czy zmienna nazywa się m czy j nie ma znaczenia.

edit:
7 sekund...

Bardzo ogromnie dziękuję.

Dokładnie przeanalizowałem algorytm. Zrobiłem na przykładzie i wyszło, co miało być :) U mnie jeszcze krucho z pisaniem, a z odczytywaniem problemów nie mam. Muszę jeszcze dalej poćwiczyć.

Właśnie zastanawia mnie jedno, bo jeśli mielibyśmy A=[-7,0,2,4,5]. Istnieją dwa indeksy - T[i]=i. Mimo, to algorytm zwróci tylko 5. A z 4 nic nie zrobi?

Zauważ że w definicji problemu masz napisane że "sprawdza czy istnieje taki indeks" a nie "zwraca wszystkie takie indeksy" ;)