Реализация рекурсивного бинарного поиска в массиве на СИ?

Question

[Dreaded]

Прохожу курс CS50 , задача стоит реализовать рекурсивный бинарный поиск в упорядоченном массиве на СИ
По условиям задачи, декларацию функции менять нельзя. То есть прототип должен выглядеть именно так:

bool search(int value, int values[], int n)

где value - искомое значение, int values[] - массив значений, int n - количество элементов в массиве

Вот написанный мной код. Если искомое число попадает на середину массива - всё отлично находится. Но в случае если число справа или слева середины - функция возвращает false :(
Что я делаю не так?

bool search(int value, int values[], int n)
{
    //проверим количество элементов в массиве
    if (n <= 0)
        return false;
    //Находим "середину массива"
    int middle=n/2;
    //Проверяем, вдруг искомое значение попало на середину. На этом этапе всё работает.
    if (value==values[middle-1])
        return true;
    //Проверяем справа, или слева находится искомое значение. Вот тут я делаю что то неправильно :(
    else if (value > values[middle-1])
         //если значение справа - передаем в функцию адрес элемента следующего за middle,
        // и вычитаем из общего количества элементов те, что остались слева
        search(value, & values[middle+1], n-middle);  

    else if (value < values[middle-1])
         // если значение слева, то передаем в функцию массив с самого начала, 
        //но количество элементов ограничиваем лишь теми, что остались слева.
        search(value, values, middle-1); 
   else return false;

}

Comments

[ArXen42]

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

return search(value, & values[middle+1], n-middle);

вместо простого выязова.

[Dreaded]

Георгий Пелагейкин, блин, как всё просто оказалось, а я уже с час голову ломаю :(
Спасибо!

Answer 1

[ArXen42]

Немного модифицирую ответ devalone, т.к. в нем, кажется, небольшая ошибка с размером массива во втором вызове:

bool search(int value, int values[], int n)
{
	//проверим количество элементов в массиве
	if (n <= 0)
		return false;

	//Находим "середину массива"
	int middle = n/2;
	if (value > values[middle])
		return search(value, values + middle + 1, n - middle - 1);
	else if (value < values[middle])
		return search(value, values, middle);

	return true;
}

Comments

[devalone]

Да, точно, спасибо. Исправил у себя.

[Dreaded]

Да, всё верно, пока анализировал код devalone вы уже нашли ошибку!
Спасибо !

[ArXen42]

Вот вроде простая штука этот бинпоиск, а вечно в нем ошибки простые можно сделать)

Answer 2

[devalone]

bool search(int value, int values[], int n)
{
    //проверим количество элементов в массиве
    if (n <= 0)
        return false;
        
    //Находим "середину массива"
    int middle=n/2;
    if (value > values[middle])
        return search(value, &values[middle + 1], n - middle - 1);
    else if (value < values[middle])
        return search(value, values, middle);

    return true;
}

Comments

[Dreaded]

Ваш код, безусловно лучше чем мой, но к сожалению, тоже не идеален.
На вот таком наборе чисел - он работает не корректно {27,28,29,30}, в случае если мы ищем 28

В то время как мой код корректно находит 28 в последовательности данной выше, но не находит 28 в следующих двух массивах {26,27,28,29} {27,28,29}

[devalone]

Dreaded, теперь находит, как правильно указал товарищ в соседнем ответе, у меня была ошибка :)