BINARNA PRETRAGA
Neka je dat niz od n elemenata. Neka je npr n=10;
int A[10] = {2, 3, -1, 4, 6, 33, 12, 4, 5, 6, 8}
Postavimo sledeći problem: Proveriti da li niz sadrži element 33.
Ovo možemo da uradimo tako što ćemo prolaskom kroz sve elemente niza redom proveravati kroz cikluse, da li je tekući element jednak sa 33. Ako ga pronađemo prekidamo ciklus.
bool pronadjen=false;
for(int i=0; i<n; i++)
{
if(A[ i ]==33)
{
pronadjen=true;
break;
}
}
Ovo je način koji predstavlja LINEARNU PRETRAGU elementa niza
U slučaju da u nizu nema traženog elementa uradiće se onoliko iteracija, koliko je n. U ovom primeru to je „samo“ puta. Postavlja se pitanje šta u slučuju da je broj elemenata niza mnogo veći. Vreme izvršavanja koda, bi u tom slučaju bilo preveliko. Efikasniji način bi bio korišćenjem
BINARNE PRETRAGE.
Pretpostavimo da je učitan niz od n elemenata V[n].
Niz mora biti uređen(sortiran). Ako nije prvo se mora sortirati.
Proveravamo da li se X nalazi u nizu. Algoritam se sastoji u tome da prolazeći kroz petlju proverimo da li traženi element jednak srednjem elementu.
Ako jeste, pronađen je i pretraga se završava. Ako je traženi element X manji od srednjeg elementa proveravanog niza S onda se on nalazi u levoj polovini niza, a ako je veći onda u desnoj. U sledećoj iteraciji proveravamo samo onu polovinu niza, u kojoj se može naći traženi element. Dakle gornja granica za proveru je prethodna srednja vrednost niza. Ovaj postupak se ponavlja sve dok ne pronađemo traženi element
int A[10] = {2, 3, -1, 4, 6, 33, 12, 4, 5, 6, 8}
Postavimo sledeći problem: Proveriti da li niz sadrži element 33.
Ovo možemo da uradimo tako što ćemo prolaskom kroz sve elemente niza redom proveravati kroz cikluse, da li je tekući element jednak sa 33. Ako ga pronađemo prekidamo ciklus.
bool pronadjen=false;
for(int i=0; i<n; i++)
{
if(A[ i ]==33)
{
pronadjen=true;
break;
}
}
Ovo je način koji predstavlja LINEARNU PRETRAGU elementa niza
U slučaju da u nizu nema traženog elementa uradiće se onoliko iteracija, koliko je n. U ovom primeru to je „samo“ puta. Postavlja se pitanje šta u slučuju da je broj elemenata niza mnogo veći. Vreme izvršavanja koda, bi u tom slučaju bilo preveliko. Efikasniji način bi bio korišćenjem
BINARNE PRETRAGE.
Pretpostavimo da je učitan niz od n elemenata V[n].
Niz mora biti uređen(sortiran). Ako nije prvo se mora sortirati.
Proveravamo da li se X nalazi u nizu. Algoritam se sastoji u tome da prolazeći kroz petlju proverimo da li traženi element jednak srednjem elementu.
Ako jeste, pronađen je i pretraga se završava. Ako je traženi element X manji od srednjeg elementa proveravanog niza S onda se on nalazi u levoj polovini niza, a ako je veći onda u desnoj. U sledećoj iteraciji proveravamo samo onu polovinu niza, u kojoj se može naći traženi element. Dakle gornja granica za proveru je prethodna srednja vrednost niza. Ovaj postupak se ponavlja sve dok ne pronađemo traženi element
/* Pretrazujemo interval [l, d] */
int l = 0;
int d = n-1;
/* Sve dok interval [l, d] nije prazan */
while (l <= d)
{
/* Srednja pozicija intervala [l, d] */
int s = (l+d)/2;
/* Ispitujemo odnos x i srednjeg elementa a[s]*/
if (x == a[s])
/* Element je pronadjen */
return s;
else if (x < a[s])
{
/* Pretrazujemo interval [l, s-1] */
d = s-1;
}
else
{
/* Pretrazujemo interval [s+1, d] */
l = s+1;
}
}
int l = 0;
int d = n-1;
/* Sve dok interval [l, d] nije prazan */
while (l <= d)
{
/* Srednja pozicija intervala [l, d] */
int s = (l+d)/2;
/* Ispitujemo odnos x i srednjeg elementa a[s]*/
if (x == a[s])
/* Element je pronadjen */
return s;
else if (x < a[s])
{
/* Pretrazujemo interval [l, s-1] */
d = s-1;
}
else
{
/* Pretrazujemo interval [s+1, d] */
l = s+1;
}
}
primer 1:
Napisati program koji sa standardnog ulaza unosi pomoću funkcije scanf nisku sa ne više od 20 karaktera i proverava da li niska sadrži znak @
Zadatak rešavamo pomoću Linearne pretrage:
#include <iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int main()
{
char a[21];
scanf("%s",&a);
bool pronadjen=false;
int poz=0;
for(int i=0; i<strlen(a); i++){
if(a[i]=='@'){
pronadjen=true;
poz=i;
break;
}
}
if(pronadjen){
printf("Karakter @ je na poziciji %d",poz);
}
else{
printf("karakter nije pronađen");
}
return 0;
}
Ovde se koristi niz karaktera tipa char, koji je učitan koristeći funkciju scanf. Ovde niska karaktera ne mora da bude uređena za razliku od binarne pretrage koja zahteva da niz prethodno bude sortiran. Obratiti pažnju da je dužina niza dobijena pomoću standardne funkcije strlen iz standardnog zaglavlja <string.h>
Napisati program koji sa standardnog ulaza unosi pomoću funkcije scanf nisku sa ne više od 20 karaktera i proverava da li niska sadrži znak @
Zadatak rešavamo pomoću Linearne pretrage:
#include <iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int main()
{
char a[21];
scanf("%s",&a);
bool pronadjen=false;
int poz=0;
for(int i=0; i<strlen(a); i++){
if(a[i]=='@'){
pronadjen=true;
poz=i;
break;
}
}
if(pronadjen){
printf("Karakter @ je na poziciji %d",poz);
}
else{
printf("karakter nije pronađen");
}
return 0;
}
Ovde se koristi niz karaktera tipa char, koji je učitan koristeći funkciju scanf. Ovde niska karaktera ne mora da bude uređena za razliku od binarne pretrage koja zahteva da niz prethodno bude sortiran. Obratiti pažnju da je dužina niza dobijena pomoću standardne funkcije strlen iz standardnog zaglavlja <string.h>
primer 2:
Napisati program koji sa standardnog ulaza unosi pomoću funkcije scanf leksikografski uređenu nisku sa ne više od 20 karaktera i proverava da li niska sadrži znak @. Zadatak uraditi korišćenjem binarne pretrage
rešenje: Pretpostavimo da je uneta niska karaktera uređena po leksikografskom redosledu. Da nije, onda bi prvo to morali da uradimo.
Koristimo algoritam Binarne pretrage gore opisan, da utvrdimo da li karakter ‘q’ postoji, i ako postoji na kojoj je poziciji.
#include <iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
/*
primer 1: Napisati program koji sa standardnog ulaza unosi pomoću funkcije scanf nisku sa ne više od 20 karaktera
i proverava da li niska sadrži znak q
*/
int main()
{
char a[21], x;
scanf("%s", &a);
bool pronadjen=false;
int poz=0;
x='q';
int n=strlen(a);
/* Pretrazujemo interval [l, d] */
int l=0,d=n-1;
/* Sve dok interval [l, d] nije prazan */
while(l<=d){
/* Srednja pozicija intervala [l, d] */
int s=(l+d)/2;
if (x==a[s]){
/* Element je pronadjen */
poz=s;
pronadjen = true;
break;
}
else if(x<a[s]){
/* Pretrazujemo interval [l, s-1] */
d=s-1;
}
else{
/* Pretrazujemo interval [s+1, d] */
l=s+1;
}
}
if(pronadjen){
printf("Karakter @ je na poziciji %d", poz);
}
else{
printf("karakter nije pronađen");
}
return 0;
}
Napisati program koji sa standardnog ulaza unosi pomoću funkcije scanf leksikografski uređenu nisku sa ne više od 20 karaktera i proverava da li niska sadrži znak @. Zadatak uraditi korišćenjem binarne pretrage
rešenje: Pretpostavimo da je uneta niska karaktera uređena po leksikografskom redosledu. Da nije, onda bi prvo to morali da uradimo.
Koristimo algoritam Binarne pretrage gore opisan, da utvrdimo da li karakter ‘q’ postoji, i ako postoji na kojoj je poziciji.
#include <iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
/*
primer 1: Napisati program koji sa standardnog ulaza unosi pomoću funkcije scanf nisku sa ne više od 20 karaktera
i proverava da li niska sadrži znak q
*/
int main()
{
char a[21], x;
scanf("%s", &a);
bool pronadjen=false;
int poz=0;
x='q';
int n=strlen(a);
/* Pretrazujemo interval [l, d] */
int l=0,d=n-1;
/* Sve dok interval [l, d] nije prazan */
while(l<=d){
/* Srednja pozicija intervala [l, d] */
int s=(l+d)/2;
if (x==a[s]){
/* Element je pronadjen */
poz=s;
pronadjen = true;
break;
}
else if(x<a[s]){
/* Pretrazujemo interval [l, s-1] */
d=s-1;
}
else{
/* Pretrazujemo interval [s+1, d] */
l=s+1;
}
}
if(pronadjen){
printf("Karakter @ je na poziciji %d", poz);
}
else{
printf("karakter nije pronađen");
}
return 0;
}
|
Prethodno
|< Sortiranje nizova |
Sledeće
Rekurzivni algoritmi >| |