[es] - Binary search u Cu??

lord_NIKON
Milenko Jovanovic
Kula/Novi Sad

Član broj: 31822
Poruke: 83
*.dialup.neobee.net.

Jabber: nikon4@jabber.org

Profil

Binary search u Cu??

^{26.12.2005. u 18:34}

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

_{[Ovu poruku je menjao lord_NIKON dana 26.12.2005. u 19:35 GMT+1]}

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

^{26.12.2005. u 18:34}

Goran Arandjelovic
Beograd

Moderator
Član broj: 29116
Poruke: 368
*.49.EUnet.yu.

Sajt: www.cpplang.com

Profil

Re: Binary search u Cu??

^{26.12.2005. u 23:17}

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);
}

_{[Ovu poruku je menjao Goran Arandjelovic dana 27.12.2005. u 00:23 GMT+1]}

http://www.cpplang.com

^{26.12.2005. u 23:17}