Ist es möglich, bei einem binären Suchalgorithmus nur einen Vergleich pro Iteration durchzuführen?

Question

Beim binären Suchalgorithmus gibt es zwei Vergleiche:

if (key == a[mid]) then found;

else if (key < a[mid]) then binary_search(a[],left,mid-1);
      else binary_search(a[],mid+1,right);

Gibt es einen Weg, wie ich nur einen Vergleich anstelle der beiden oben genannten durchführen kann?

--

Gracias

Alok.Kr.

Answer 1

for (step = 0; step < n; step <<= 1);

for (i = 0; step; step >>= 1)
    if (i + step < n && v[i + step] <= x)
        i += step;

Answer 2

Ok, das war eine Interviewfrage in Adobe, und ich habe gerade versucht, herauszufinden, wie man das macht.

Jetzt habe ich die Lösung gefunden, also poste ich

void binary_search (int a[] , int low ,  int high , int key )
{
    int mid = (low+high)/2;

    if (key == a[mid]) {
        printf ("Number Found\n");
        return;
    }

    else {
        int sign = Calc_sign (key-a[mid]);
        low = low*sign + (1-sign)*mid;
        high = mid*sign + (1-sign)*right;
        binary_search (a,low,high,key);
    }
}

int Calc_sign(int a) 
{
     return ( (a & 80000000) >> 31);
}

Im Code wird also nur ein Vergleich durchgeführt, um zu prüfen, ob der Schlüsselwert dem mittleren Element entspricht.

--

Gracias

Alok Kr.