C ++ Рекурсивный бинарный поиск с тремя параметрами
Я на 99% уверен, что моя проблема в том, что я устанавливаю низкий уровень на ноль при каждом запуске. Но я не уверен, как сохранить низкий уровень в соответствии с низким индексом независимо от глубины моей рекурсии. Если бы он точно показал мне индекс низкого индекса, я не думаю, что у меня возникнет проблема.
Вот мой код до сих пор:
int recBSearch(vector<int> v, int size, int item)
{
int index = size / 2;
int curr = v[index];
int low = 0;
int high = size -1;
if (v[index] == item)
return index;
else if (v[index] > item)
{
high = index;
index = (high+low)/2;
size = high - low;
return recBSearch(v, size, item);
}
else if (v[index] < item)
{
low = index;
index = (high+low)/2;
size = high - low;
return recBSearch(v, size, item);
}
return -1;
}
Решение
Это не сработает, когда вы пытаетесь выполнить поиск в верхней половине вектора, потому что вам действительно нужно создать фрагмент вектора.
Уже есть бинарный поиск, но если вы решили написать свой собственный, используйте итератор-диапазон в параметрах. (Вы можете передать два простых итератора или увеличить диапазон).
Вы хотите -1, если не найдено иное местоположение итератора, поэтому в вашем срезе (диапазоне итераторов) вам нужно будет указать начальный индекс, если он найден.
В качестве альтернативы вы также можете передать вектор (по константной ссылке) и диапазон, в котором вы хотите искать.
Ваша последняя строка недоступна. Вместо этого это должно быть завершающее условие вашей рекурсии, прежде чем вы сделаете какую-либо оценку. (Если ваш диапазон пуст)
Версия, которая будет повторяться путем передачи по ссылке и с использованием порядковых номеров (самая простая), будет выглядеть следующим образом:
int recBSearch( std::vector<int> const& vec, int start, int end, int value )
{
if( start == end )
{
return -1;
}
int index = (start + end) / 2;
// continue from here
}
end будет означать «один за последним элементом», поэтому, если вектор имеет размер 5, первая итерация пройдет 0 и 5. Если вектор пуст, вы передаете 0 и 0.
В качестве упражнения «можно ли это сделать с 3 параметрами»?
Да…
typedef std::vector<int>::const_iterator citer;
int recBSearch( citer start, citer end, int value )
{
if( start == end )
{
return -1;
}
citer middle = start + (end-start)/2;
if( *value == *middle )
{
return middle - start;
}
else if ( *value < *middle )
{
return recBSearch( start, middle, value );
}
else // note the change here
{
int res = recBSearch( middle+1, end, value );
if( res == -1 )
return -1;
else
return res + 1 + (middle-start);
}
}
Другие решения
Если вы хотите сделать это рекурсивным, ваш метод должен принять диапазон поиска в качестве параметров. В противном случае вы не можете отследить, где искать в рукурсивном вызове, предполагая, что вы всегда задаете полный вектор функции.
Таким образом, подпись вашего метода должна быть такой:
int recBSearch(vector<int> v, int first, int last, int item)
Бинарный поиск в основном работает путем деления вашего диапазона на 2 половины и поиска в каждой из них. Ваш код показывает, что вы работаете в нижней половине для обеих ваших ветвей. Вам нужно перейти на рекурсивный вызов более высокой половины вашего v вектор во втором else if так же как size/2 вместо size,