Линейный поиск по вектору

Question

У меня есть тесты для прохождения онлайн, используя мои созданные методы. У меня есть ощущение, что есть проблема с одним из тестов. Последний, который я не могу пройти. Вот тест -

TEST_CASE ("Linear Search With Self-Organization 3") {
  int searchKey = 191;

  vector<int> searchArray(500);
  for (int i = 0; i < 500; i++) {
    searchArray[i] = i + 1;
  }
  random_shuffle(searchArray.begin(), searchArray.end());

  bool result, result2;
  result = linearSearchSO(searchArray, searchKey);
  int searchKey2 = 243;
  result2 = linearSearchSO(searchArray, searchKey2);

  REQUIRE (result == true);
  REQUIRE (result2 == true);
  REQUIRE (verifySearchArray(searchArray) == true);
  REQUIRE (searchArray[0] == searchKey2);
  REQUIRE (searchArray[1] == searchKey);
  REQUIRE (searchArray.size() == 500);
}

Рассматриваемый метод - linearSearchSO.

bool linearSearchSO(vector<int> & inputArr, int searchKey) {
   printArray(inputArr);
   for(int i=0; i < inputArr.size(); i++) {
      int temp = inputArr[0];
      if (inputArr[i] == searchKey) {
         inputArr[0] = inputArr[i];
         inputArr[i] = temp;
         printArray(inputArr);
         return true;
      }
   }
   return false; 
}

Стоит отметить, что этот метод прошел все 3 других необходимых теста. Как вы можете видеть в тесте, мой преподаватель дважды вызывал этот метод, передавая два разных значения. Идея состоит в том, что существует вектор из 500 чисел. В этом случае он рандомизирует числа. Лучший способ объяснить мне, что происходит, - это если он не рандомизируется, а числа просто перечисляются 1-500. Метод вызывается, и я начинаю с запрошенного числа 191, я перемещаю его в начало вектора. Теперь он читает 191, 2, 3, 4 и т. Д. c. 190, 1, 192 и др. c. Поэтому он снова вызывает метод и хочет, чтобы 243 был перемещен вперед. Его тест требует, чтобы результат был 243, 191, 2, 3, 4. Однако мой код меняет местами 191 на 243. Мой результат теперь гласит: 243, 2, 3, 4 и т. Д. c. 242, 191, 244, 245 и т. c.

Каждый второй тест состоит в том, чтобы просто взять один номер и переместить его вперед, затем тест проверяет, что каждый номер находится в правильном положении. Мой вопрос заключается в том, есть ли для меня способ достичь 243, 191, 2, 3 ... без путаницы в каждом втором тесте, который я прошел, используя только эту функцию linearSearch? или есть проблема с тестом, и он просто сделал ошибку.

РЕДАКТИРОВАТЬ- Фактический вопрос, заданный для этого теста. Вопрос 4 Самоорганизующийся алгоритм поиска - это алгоритм, который переставляет элементы в коллекции таким образом, что те элементы, которые часто ищутся, скорее всего, будут найдены быстрее при поиске. Измените алгоритм обучения для линейного поиска таким образом, чтобы каждый раз, когда элемент находился в массиве, этот элемент обменивался с элементом в начале массива.

Answer 1

Если я правильно понял, вам нужно что-то вроде следующего

#include <iostream>
#include <vector>

bool linearSearchSO( std::vector<int> & inputArr, int searchKey ) 
{
    bool success = false;

    auto it = inputArr.begin();

    while  (  it != inputArr.end() && *it != searchKey ) ++it;

    if ( ( success = it != inputArr.end() ) )
    {
        int value = *it;
        inputArr.erase( it );
        inputArr.insert( inputArr.begin(), value );
    }

    return success;
}

int main()
{
    std::vector<int> inputArr = { 1, 2, 3, 4, 5 };

    for ( const auto &item : inputArr )
    {
        std::cout << item << ' ';
    }
    std::cout << '\n';

    linearSearchSO( inputArr, 3 );   

    for ( const auto &item : inputArr )
    {
        std::cout << item << ' ';
    }
    std::cout << '\n';
}

Вывод программы:

1 2 3 4 5 
3 1 2 4 5 

Обратите внимание, что вместо написания вручную al oop в функцию вы можете использовать стандартный алгоритм std::find.