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:
gdzie:
- X — szukana wartość,
- N — długość tablicy danych,
- dane — tablica typu int zawierające uporządkowane dane.
Funkcja zwraca wartości:
- i ∈{0,1,…,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).
3 Wersja PDF tego dokumentu…
Wersja: 19 z drobnymi modyfikacjami! data ostatniej modyfikacji 2016-03-29 07:57:01 +0200