24.11.2.24011760. Napisati program koji će na primjeru jednog fiksnog sortiranog niza od 50 elemenata i broja “n“ unesenog sa tastature postupkom binarne pretrage ispisati poziciju gdje se broj “n“ nalazi unutar niza (odnosno činjenicu da broj “n“ nije pronađen unutar niza). Također je potrebno ispisati u koliko koraka je pronađen broj (odnosno koliko koraka je utrošeno prije nego što je ustanovljeno da se broj ne nalazi unutar niza).

Opis rješenja:

Listing programa:

#include <iostream>
#include <conio.h>
#include <cstdlib>
#include <ctime>

using namespace std;
void generirajniz(int *p1,int *p2,int a,int b){
while(p1<p2){
   *p1=a+rand()%(b-a+1);
    p1++;
    }
}
void sortniz2(int *p,int *k){
if(p+1>=k)return;
int pivot=*(p+rand()%(k-p));
int *l=p,*d=k-1;
    while(l<=d){
        while(*l>pivot)l++;
        while(*d<pivot)d--;
        if(l<=d){
            int a=*l;
            *l=*d;
            *d=a;
            l++;
            d--;
        }
    }
sortniz2(p,d+1);
sortniz2(l,k);
}


int main(){
srand(time(0));
int a[50];
int A,B;
cin>>A>>B;
generirajniz(a,a+50,A,B);
sortniz2(a,a+50);
int n;
cin>>n;
int l(0),d(49),s(-1),k(0);
while(l<=d){
    int i=(l+d)/2;
    if(a[i]==n){
        k++;
        s=i+1;
        break;
    }
    else if(a[i]<n)
        d=i-1;
    else
        l=i+1;
k++;
}
if(s!=-1)
    cout<<s<<endl<<k;
else
    cout<<"no!"<<endl<<k;
    
getch();    
return 0;
}

Ispis na ekranu:

Riješeni zadaci 2    Index