Opis programu

• Program ilustruje działanie algorytmu wyszukiwania elementu w zbiorze uporządkowanym metodą przez połowienie.
• Algorytm opisany w podręczniku w punkcie 4 na stronie 69.
• Wersja "PODRĘCZNIKOWA" opisana w podręczniku na stronach 103-104.

Kod programu:

#include <iostream>
using namespace std;

const int N = 10; //ilość liczb

int liczby[N]; //tablica dla liczb

// funkcja wprowadzająca do programu liczby do posortowania
void wprowadzDane()
{
	int i;
	cout << "\n Wyszukiwanie elementu w zbiorze uporzadkowanym";
	cout << "\nwersja podrecznikowa, str 101-102\n";
	cout << "\nIlosc liczb: " << N << "\n";
	// pętla wprowadzająca liczby do posortowania
	for (i = 0; i < N; i++)
	{
		cout << "podaj liczbe nr " << i << " (musi byc >= od liczby podanej poprzednio ): ";
		cin >> liczby[i];
	}
}

//funkcja wyszukująca pozycję szukanej wartosci w tablicy liczby
int znajdzDana(int wartosc)
{
	int poczatek, koniec, srodek;
	poczatek = 0;
	koniec = N;
	do
	{
		srodek = (poczatek + koniec) / 2;
		if (liczby[srodek] == wartosc) 
			return srodek;
		else
		{
			if (wartosc < liczby[srodek]) koniec = srodek - 1;
			else poczatek = srodek + 1;
		}
	} while (poczatek <= koniec);
	return -1;
}

//program główny
int main() {
	int wartosc, pozycja;
	wprowadzDane();
	cout << "\n Podaj liczbe do wyszukania:"; cin >> wartosc;
	pozycja = znajdzDana(wartosc);
	if (pozycja >= 0) cout << "\nZnaleziono wartosc " << wartosc << " na pozycji nr " << pozycja;
	else cout << "\nNie znaleziono wartosci " << wartosc;
	return 0;
}

Użycie kodu:

• Powyższy kod można wykorzystać w środowiski Dev C++. Wystarczy utworzyć nowy projekt i wkleić ten kod zamiast istniejącego.
• Można też użyć kodu na jednej ze stron WWW z kompilatorami on-line, na przykład na stronie: www.cpp.sh