algorytm.org

Implementacja w C/C++

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Szukanie połówkowe (binarne) - Implementacja w C/C++
Ocena użytkownikóww: *****  / 3
SłabyŚwietny
Nadesłany przez Kamil Dębowski, 06 marca 2011 17:58
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.

Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.

szukanie_polowkowe_2_c.cpp:
//Wyszukiwanie binarne
//www.algorytm.org

#include<cstdio>
#include<conio.h>	// naglowek pozwalajacy uzyc funkcji getch()

int n,t[100],x,s,indeks;

int bin_search(int l, int p)
{
	if (l>p) return -1;	// jesli l jest na prawo od p (jest większe) to nasz przedział jest pusty czyli nie znajdziemy x-a
	s=(l+p)/2;	// srodek rozpatrywanego przedzialu to srednia arytm. poczatku i konca
	if (t[s]>x) return bin_search(l,s-1);	// pod s mamy za duza liczbe, wiec musimy szukac wczesniej (bardziej na lewo)
	if (t[s]<x) return bin_search(s+1,p);	// j.w. tyle ze odwrotnie - mamy za mala liczbe, szukajmy na prawo
	return s;
}

int main()
{
	// Wczytujemy dane
	printf("Podaj wielkosc tablicy.\n");
	scanf("%d", &n);
	printf("Teraz podaj %d liczb w kolejnosci rosnacej.\n", n);
	for (int i=0; i<n; i++)
		scanf("%d", &t[i]);
	printf("Podaj liczbe do znalezienia.\n");
	scanf("%d", &x);

	indeks=bin_search(0,n-1);	// szukamy w calej tablicy (czyli od indeksu 0 do ostatniego n-1)
	if (indeks==-1) printf("Nie ma takiej liczby.\n");	// program zwrocil (return) -1 jesli przedzial byl juz pusty
	else printf("%d ma indeks %d (indeksujemy od 0).\n", x, indeks);

	printf("Wcisniecie dowolnego klawisza zakonczy program.");
	getch();
	return 0;
}
Dodaj komentarz