Wyszukiwanie

Oznaczenia:

• a - tablica z danymi
• value - szukany element
• left - indeks lewego końca obszaru wyszukiwania
• right - indeks prawego końca obszaru wyszukiwania

Tablice nieuporządkowane

Wyszukiwanie liniowe

linear_search(a, value, left, right)
    for i=left to right
      if a[i]==value 
         return i
    return nie_znaleziono

Tablice uporządkowane

Wyszukiwanie binarne

binary_search(a, value, left, right)
    while left <= right
        mid = (left+right)/2
        if a[mid] == value
            return mid
        else if value < a[mid]
            right = mid-1
        else if value > a[mid]
            left = mid+1
    return nie_znaleziono

Wyszukiwanie interpolacyjne

  interpolation_search(a, value, left, right)  
  while a[left] < a[right]
    mid=(value-a[left])/(a[right]-a[left])*(right-left)+left; 
        if mid<left or mid>right return nie_znaleziono
        if a[mid] = value
            return mid
        else if value < a[mid]
            right = mid-1
        else if value > a[mid]
            left = mid+1
  return nie_znaleziono

Przykładowa implementacja dla tablicy liczb całkowitych

interp.cpp

i ten sam program z użyciem klas:

interp2.cpp

Przykładowe zadania

• Dla uporządkowanej tablicy:
  • punktów na płaszczyźnie
  • kodów pocztowych
  • dat w formacie dzień/miesiąc/rok
  zastosuj algorytm szukania liniowego, szukania binarnego, szukania interpolacyjnego z wykorzystaniem klas i enkapsulacji.
• Zastanów się (sprawdź w literaturze) jaka jest minimalna i maksymalna liczba porównań potrzebna do znalezienia elementu w każdym z tych algorytmów.