Binary search u Cu??

[ lord_NIKON @ 26.12.2005. 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]}

[ Goran Arandjelovic @ 26.12.2005. 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]}