Endlosschleife in modifizierter binärer Suche

Question

Ich versuche eine modifizierte Version der binären Suche zu implementieren, die die Position des nächstgrößeren Wertes eines gegebenen Schlüssels aus einem sortierten Array zurückgibt.

Hier ist der Code - (LLI auf long long int bezeichnet)

lli search(vector<lli>arr,lli key) 
{ 
    lli low=0,high=arr.size() - 1,mid,pos=-1; 

    while(low<=high) 
    { 
     mid=low + (high-low)/2; 

     if(arr[mid]<key) 
      low=mid+1; 
     else{ 
       pos=mid; 
       high=mid-1; 
      } 
    } 
    return pos; 
} 

Hier arr das sortierte Array ist, und wir haben die Position des nächstgrößten Element finden als der Schlüssel im Array arr.

Ich habe dafür gesorgt, dass der Schlüssel zwischen [min (arr), max (arr)] ist, also hat pos einen Wert in [0, arr.size() - 1].

Die Methode läuft für viele Werte, die ich mir vorstellen kann, aber der Online-Richter lehnt es mit dem Fehler Zeitlimit überschritten ab. Ist hier eine Endlosschleife möglich?

Answer 1

Sie können als regulären binären Such lösen, sondern verwenden

if (arr[mid] == key){ 
    if (mid == arr.size() - 1) 
     return -1; // key was the last element, there is nothing after it 
    return mid + 1; 
}