Metoda połowienia w C++. Wyszukiwanie liczby w zbiorze uporządkowanym.

Problem:

Dany jest skończony zbiór liczb uporządkowany rosnąco. Znajdź w tym zbiorze podaną liczbę (określ jej położenie w zbiorze) metodą połowienia.

Koduj sam, ale film może Ci pomóc zrozumieć ....

W poniższym filmie:

• omówienie jak działa metoda połowienia,
• ilustracja działadnia algorytmu dla konkretnej tablicy liczb i wybranej wartości do wyszukania,
• kodowanie wersji prostej,
• kodowanie wersji, w której tablica liczb jest losowana,
• przykłady uruchomienia,
• a co jeśli szukanej liczby nie ma w zbiorze?

Do obejrzenia i przećwiczenia:

Kod w C++ w wersji podstawowej ze statyczną tablicą z filmu

#include <iostream>
using namespace std;
//zmienne globalne - pozwalają uniknąć przekazywania tablicy jako argumentu funkcji
//tablica liczb użyta w filmie
int liczby[]={1,2,7,9,12,14,18,21,32,41,48,50,52,54,60,62,71,73};
//funkcja wyszukująca pozycję szukanej wartości w tablicy liczby
int znajdzDana(int x){
	int p=0, //początek
	k=17, //koniec - w tablicy liczby jest 18 liczb
	s; //srodek
	do{
		s=(p+k)/2; //połowa przedziału
		//komunikaty:
		cout<<"<"<<p<<","<<k<<"> srodek-pozycja: "<<s<<" liczba: "<<liczby[s]<<endl;
		if(liczby[s]==x) return s; //jeśli trafiłem na szukaną liczbę, to zwracam jej pozycję w zbiorze
		else {
			if(x<liczby[s]) k=s-1; //po której stronie szukanej wartości jest środej?
			else p=s+1;
		}
	} while(p<=k); //dopóki początek <= koniec
return -1; //jeśli nie ma liczby w zbiorze, to zwracam -1
}
//program główny
int main() {
	int wartosc, pozycja;
	cout << "liczby:\n";
	for(int i=0; i<18; i++) cout << liczby[i] << " "; //wyświetlenie liczb z tablicy
	cout << "\nPodaj liczbe do wyszukania:"; cin >> wartosc; //wczytanie liczby do wyszukania
	pozycja = znajdzDana(wartosc); //użycie funkcji znajdzDana()
	//komunikaty końcowe:
	if(pozycja >=0) cout << "\nZnaleziono wartosc:" << wartosc << " na pozycji nr:" << pozycja << ". Jest to:" << pozycja+1 << " liczba w zbiorze.";
	else cout << "\nNie znaleziono wartosci: " << wartosc << " w zbiorze";
return 0;
}

Kod w C++ w wersji z tablicą liczb losowych

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
//zmienne globalne - pozwalają uniknąć przekazywania tablicy jako argumentu funkcji
const int N = 300; //ILOŚĆ LICZB - TO MOŻESZ ZMIENIAĆ
int liczby[N]; //tablica dla liczb
// funkcja wprowadzająca do programu rosnące liczby do przeszukania
void wprowadzDane() {
	int i;
	liczby[0]=rand()%10;
	for (i=1; i<N; i++)	liczby[i] = liczby[i-1] + rand()%10+1;
	cout << "\nzbior liczb do przeszukania: ";
	for (i=0; i<N; i++) cout << liczby[i] << " ";
}
//funkcja wyszukująca pozycję szukanej wartości w tablicy liczby
int znajdzDana(int x){
	int p=0, k=N-1, s;
	do{
		s=(p+k)/2;
		cout<<"<"<<p<<","<<k<<"> srodek-pozycja: "<<s<<" liczba: "<<liczby[s]<<endl;
		if(liczby[s]==x) return s;
		else {
			if(x<liczby[s]) k=s-1;
			else p=s+1;
		}		
	}while(p<=k);
	return -1;
}
//program główny
int main() {
	srand(time(NULL)); //ustawienie "maszyny losującej"
	int wartosc, pozycja;
	wprowadzDane();
	
	cout << "\nPodaj liczbe do wyszukania:"; cin >> wartosc;
	pozycja = znajdzDana(wartosc);
	
	if (pozycja >= 0) cout << "\nZnaleziono wartosc " << wartosc << " na pozycji nr " << pozycja << ". Jest to " << pozycja+1 << " liczba w zbiorze.";
	else cout << "\nNie znaleziono wartosci: " << wartosc << " w zbiorze";
	return 0;
}

Użycie kodu:

• Powyższy kod można wykorzystać w środowisku Dev C++ lub innym. 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