Binäre Suche C++ (was ist der Fehler in diesem Code)

Question

Ich löste die binäre Suche Tutorial auf Hackerearth, aber anscheinend stimmt etwas nicht ... Das Eingabeformat ist wie folgt N = keine Elemente in Array Elemente in aufsteigend Q = Anzahl der Testfälle Elemente in den q Testfälle

#include <iostream> 
using namespace std; 
int main() 
{ 
    int n;cin>>n; 
    int ar[n];for(int y=0;y<n;y++) cin>>ar[y]; 
    int q;cin>>q; 

    for(int u=0;u<q;u++) 
    { 
     int j;cin>>j; 
     int low=0,high=n-1,mid=(low+high)/2; 

     while(low<high) 
     { 
      mid=(low+high)/2; 
      if(ar[mid]<j) low=mid+1; 
      if(ar[mid]>j) high=mid-1; 
     } 

     cout<<mid-1<<endl; 
    } 
    return 0; 
} 

Bearbeiten gefunden werden:

1. Warum gibt es so viel Hass für die Erklärung variabler Größe Array .. Es ist so viel effektiver zu schreiben als Vektor ... Und es ist völlig legal nach C++ 99 Standard .. Ich benutze dies in C++ 11 Standard und Alle meine Programme arbeiten mit Arrays variabler Größe.

2. Vielen Dank für den Hinweis auf den Fehler. Der Fall für j == ar [mid] ist nicht behandelt. Der Code sollte danach funktionieren.

3. Vergessen Sie die Darstellung der Antwort und Eingänge bekommen .. völlig unnötig, wie ich bereits erwähnt dies ein Problem auf hackerearth ist .. es auto ist geprüft .. Die Antwort verdirbt das Ausgabeformat präsentiert

4. Dies war Meine erste Frage hier, die Community war sehr hilfreich. :). Auch deshalb ist es so schwierig Code einzufügen .. Ich Insert Code versucht, kopieren und einfügen in ihm .. aber es hat nicht funktioniert .. Ich musste manuell Einzug alles zu 4 Leerzeichen :(

Answer 1

Es gibt 3 Dinge, die Sie sollten diesen Code Arbeit machen ändern.

1. Sie den Fall zu behandeln vergessen, wenn ar[mid]==j. In diesem Fall while(low<high) die while-Schleife unendlich werden wird.

2. cout<<mid-1<<endl; Diese Linie bedeutet, dass Ihr während Schleife stellt sicher, dass mid immer auf einen Index mit größerem Wert zeigt, was nicht der Fall ist, wenn man die while-Schleife schreibt.

3. int n; cin>>n; int ar[n]; Dies ist eine wirklich schlechte Übung, da n keine Konstante ist. Versuchen Sie es mit std::vector<int> ar(n) statt int ar[n]

Sie die Suchteil wie folgt bearbeiten:

int low=0,high=n-1,mid; 
while(low<high) 
{ 
    mid=(low+high)/2; 
    if(ar[mid]>j) high=mid-1; 
    else low=mid+1; 
} 
if(high>=1 && high<=n && ar[high-1]==j) cout<<(high-1)<<endl; 
else { // you didnt find the value} 

Answer 2

Zunächst einmal können Sie erklären, nicht variabler Größe Array.

Und machen die binäre Suche wie folgt,

int j; 
    cin >> j; 

    int low = 0, high = n - 1, mid = (low + high)/2; 

    while (low<=high) 
    { 
     mid = (low + high)/2; 
     if (ar[mid] == j) 
      break; 

     if (ar[mid]<j) low = mid + 1; 
     if (ar[mid]>j) high = mid - 1; 
    } 
    if (ar[mid] == j) 
     cout << j << " is found and index is = " << mid << endl; 
    else 
     cout << j << " is not found" << endl;