Двоичный поиск C++ (что является недостатком в этом коде)

Question

Я решал учебник по двоичному поиску на хакереарте, но, видимо, что-то не так ... Формат ввода выглядит следующим образом: N = нет элементов в массиве элементов в по возрастанию Q = число тестов элементов можно найти в д тестовых

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

Редактировать:

1. Почему так много ненависти к объявлению массива переменных размеров. Это гораздо эффективнее писать, чем вектор ... И он совершенно легален в соответствии со стандартом C++ 99. Я использую это в стандарте C++ 11 и все мои программы работают с массивом переменных размеров.

2. Благодарим за указание недостатка. Случай j == ar [mid] не обрабатывается. После этого код должен работать.

3. Забудьте о представлении ответа и получать материалы .. совершенно не нужно, как я уже говорил, что это проблема на hackerearth .. это авто проверено .. представление ответа на вызов портит выходной формат

4. Это было мой первый вопрос здесь, сообщество было очень полезно. :). Кроме того, почему так трудно вставить код .. Я попытался вставить код и скопировать вставить в него .. но он не работает .. Я должен был вручную отступ всех 4 пространств :(

Answer 1

Есть 3 вещи, которые вы должны изменить, чтобы сделать этот код работать.

1. вы забыли обработать случай, когда ar[mid]==j. в этом случае цикл, пока while(low<high) станет бесконечным.

2. cout<<mid-1<<endl; Эта линия означает, что ваше время петля что в середине всегда указывается индекс с большим значением, что не так, учитывая то, как вы написали цикл while.

3. int n; cin>>n; int ar[n]; Это действительно плохая практика, поскольку n не является постоянной. Попробуйте использовать std::vector<int> ar(n) вместо int ar[n]

вы можете редактировать поиск часть, как это:

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

Прежде всего, Вы не можете объявить массив переменного размера.

И сделать бинарный поиск следующим образом,

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;