Неожиданный результат линейного поиска

Пожалуйста, найдите мой код ниже для линейного поиска. Функция бинарного поиска дает правильный результат. Но после стресс-тестирования я не получаю правильный результат линейного поиска. При реализации того же кода для линейного поиска с теми же входными данными (тестовым набором), что и при стресс-тестировании, код дает правильный результат.

int linear_search(const vector<int> &a, int x) 
{
  for (int i = 0; i < a.size(); ++i) 
  {
    if (a[i] == x)
    {
      return i;
    }
  }
  return -1;
}

основная функция

int main() {
   while(true)
   {
     int n=5;
   vector<int> a(n);
   for (size_t i = 0; i < n; i++) {
     int b = rand() % 5 + 1;
     a.push_back(b);
   }
   for (size_t i = 0; i < n; i++) {
     std::cout<<a[i]<<" ";
   }
   std::cout<<"\n";
   int x = rand() % 10 + 1;
   std::cout<<x<<"\n";
   int l = linear_search(a,x);
   int b = binary_search(a,x);
   if(l != b)
   {

     std::cout<<l<<"\n";
     std::cout<<b<<"\n";
     break;
   }
   else
   {
     std::cout<<"Ok\n";
   }
   }
}

После запуска приведенного выше кода я получаю неправильный (неожиданный) вывод, когда случайный ввод (созданный стресс-тестированием):

0 0 0 0 0

4

Выход линейного поиска равен 5 вместо -1. Я не могу найти ошибку.


person Jarv Potter    schedule 21.04.2020    source источник
comment
Вы также забыли запустить генератор случайных чисел. Вам нужно использовать srand   -  person smac89    schedule 21.04.2020


Ответы (1)


Здесь вы создаете вектор с n элементами:

vector<int> a(n);

а затем дополнительно push_backдобавления n элементов.

В результате получается n*2 элементов в a, а в linear_search вы просматриваете их все. Я предполагаю, что 5-й индекс имеет значение 4 в этом конкретном тестовом примере.

person cigien    schedule 21.04.2020