Binary search u Cu??

Odgovori Nova tema

1 odgovor
4.033 pregleda

Binary search u Cu?? 26.12.2005. u 19:34 · pre 254 meseca #1

Code:

int binsearch(int x, int v[], int n)
{
    int low, high, mid;
    low = 0;
    high = n - 1;
    while(low <= high) {
           mid = (low + high)/2;
        if(x < v[mid])
            high = mid + 1; // <-- zasto se dodaje +1
        if(x > v[mid])
            low = mid + 1;
        else
            return mid;
    }
    return -1;
}

Naime, kod kod ove funkcije mi je jasan. Algoritam trazi vrednost x u nizu v, dok n predstavlja broj elemenata niza.
Ono sto mi nije jasno je sledece, zasto se posle uporedjivanja vrednosti x sa nekom vrednosti iz niza v , high postavlja na mid +1.
Ja sam kontao, zato sto imamo deljenje int brojeva pri odredjivanju vrednosti mid. Posto bi kod takvog deljenja svaki ostatak nestao, dodajemo jedinicu da bi povecali vrednost ukoliko je doslo do gubljenja vrednosti.
Ispravite me ako nisam u pravu

Potpis

www.safsrbija.com/forum | www.indie-go.com/forum

"I'd rather have a bottle in front of me than a frontal lobotomy." Tom Waits

Re: Binary search u Cu?? 27.12.2005. u 00:17 · pre 254 meseca #2

Evo ti u C++-u, ali to je to...

Code:

#include <iostream>
using namespace std;

int bsearch(int x, int *v, int n);

int main(int argc, char *argv[])
{
    int x[] = {6,8,9,13,15,18,27,35}; // dakle, prvo sortiras niz
    cout << bsearch(8,x,sizeof(x)/sizeof(int)); // jasan ti je ovaj treci argument?
}

int bsearch(int x, int *v, int n)
{
    int low, high, mid;
    low = 0;
    high = n; // ovde ne treba da smanjis za 1, upravo zbog deljenja koje si pomenuo
                   // (kada se kao vrednost deljenja uvek dobije manji broj...) da bi uopste mogao
                   // da pronadjes poslednji element...

    while(low<=high){
      mid = (low+high)/2;
      if(x < v[mid]){
        high = mid; // nisu potrebna nikakva uvecavanja
      }
      if(x > v[mid]){
        low = mid;
      }
      if(x == v[mid]){ // trebalo je da odvojis kompletno ovaj uslov, a ne da bude u okviru ovog iznad...
         return(mid);
       }
    }
    return(-1);
}

Prijavite se da biste odgovorili u ovoj temi.Prijava Registracija

Forum kao aplikacija na telefonu

Srodne teme