Laboratorium 11

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 left<=right
    mid=(value-a[left])/(a[right].k-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

lin.cpp

Przykładowe zadania

• punktów na płaszczyźnie
• kodów pocztowych
• dat w formacie dzień/miesiąc/rok