Laboratorium 5a: Wyszukiwanie binarne — doskonalenie aplikacji

1 Wprowadzenie

Jak się wydaje większość stworzonych aplikacji jest w miarę poprawna. To czego im zazwyczaj brakuje to:

Dokładne przetestowanie. W szczególności sprawdzić należy:

tablice z danymi o długości 1 i 2 (warto też sprawdzić zachowanie algorytmu dla tablic o parzystej i nieparzystej liczbie danych),
sprawdzenie czy poprawnie znajdowane są pierwsza i ostatnia wartość z tablicy danych,
sprawdzenie czy poprawnie traktowane są szukane wartości mniejsze/większe od najmniejszej/największej wartości w tablicy.

Usunięcia wszystkich wydruków poza pętle. W tej chwili część przedstawionych programów drukuje sprzeczne informacje (lub nie drukuje nic).
Ewentualnie doprowadzenie do sytuacji, w której do „algorytmu” wyszukiwania jest tylko jedno wejście i jedno wyjście.

2 Zadania do wykonania

Wydzielenie algorytmu wyszukiwania binarnego jako osobnej funkcji, o przykładowym wywołaniu:

int bin_szuk(int X, int N, int dane[N]);

gdzie:

X — szukana wartość,
N — długość tablicy danych,
dane — tablica typu int zawierające uporządkowane dane.

Funkcja zwraca wartości:

$i \in{0,1,\ldots,N - 1}$ — znaleziono wartość na pozycji $i$,
$i < 0$ — wartości nie znaleziono.

Dodatkowo, zwracana wartość może zawierać zakodowaną informację gdzie należałoby wstawić wartość. Tu można zakodować numer przedziału, którym należy umieścić wartość:

przed zerowym elementem
między zerowym, a pierwszym,
…
między $N - 2$ a $N - 1$,
na miejscu $N$ (po $N - 1$).

Kolejnym etapem jest taka modyfikacja funkcji, aby nieznalezioną wartość dopisywała do tabeli w takim miejscu aby dane ciągle były uporządkowane rosnąco (malejąco).

Można to zrobić na dwa sposoby.

Oprócz tablicy z danymi (załóżmy, że nazywa się ona T i ma długość N deklarujemy tablicę T1 (tego samego typu co T) o długości N + 1.

Tablice T i T1 muszą być parametrami funkcji. Gdy wartość trzeba dodać przed wyjściem z funkcji dokonuje się odpowiedniego przepisania danych.

Drugi sposób jest nieco bardziej zagmatwany, ale ładniejszy. Skorzystamy z pamięci dynamicznej oraz funkcji malloc() oraz realloc().

Funkcja malloc() wywoływana jest w sposób następujący:

#include <stdlib.h>
...
int * T; // To jest nasza tablica
int N; // W N jest rozmiar tablicy
...
T = malloc(N * sizeof(int)); // Prosba o przydzial pamieci
if (T == 0) // Gdy pamiec nie może byc przydzielona
            // funkcja zwróci wartosc 0
{
    printf("Brak pamieci!\\n");
    return -1;
}

Funkcja zwraca adres (wskaźnik) początku obszaru pamięci przydzielonego tablicy z danymi. Użyjemy jej w funkcji main(). Niestety tablicom dynamiczny nie można nadawać początkowych wartości tak jak automatycznym. Nie jest to wielkim problemem, gdyż nasz program powinien teraz poradzić sobie z tablicą jednoelementową lub pustą!

Program startuje z pustą tablicą (która będzie rozszerzana dynamicznie):
```
int * T;
int N = 0;
```
Po przeczytaniu pierwszej wartości (x) program wykona następujące czynności:
```
T = malloc(1 * sizeof(int));
T[N] = x;
N++;
```
Teraz tablica ma 1 element.
Dla każdej kolejnej czytanej wartości, program sprawdza (metodą wyszukiwania binarnego), czy znajduje się ona w tablicy:
- jeżeli tak — nie robi nic, przechodzi do czytania kolejnej wartości;
- jeżeli nie — zwiększa długość tablicy o 1;
  Gdy trzeba rozmiar tablicy zwiększyć używamy funkicji realloc(). Używamy jej tak:

int * T1; // To bedzie ,,nowa’’ tablica
...
T1 = realloc(T, (N + 1) * sizeof(int))
// T to ,,stara.. tablica, a N + 1 to potrzebny rozmiar ,,nowej’’
if (T1 == 0)
// Oznacza to, ze ne udalo sie zwiekszyc rozmiaru tablicy
{
    printf("Brak pamieci!\\nEmergency exit");
    return -1;
}
else
{
    T = T1;
}
...

Używamy dodatkowej zmiennej T1 żeby w sytuacji, kiedy nie uda się przydzielić pamięci (realloc() zwraca zero!) nie stracić danych!