Написание рекурсивного бинарного поиска в C

Question

Я нашел следующий код в сети,

int binary_search(int a[], int low, int high, int target) {
    if (high < low)
        return -1;
    int middle = (low + high)/2;
    if (target < a[middle])
        return binary_search(a, low, middle-1, target);
    else if (target > a[middle])
        return binary_search(a, middle+1, high, target);
    else if (target == a[middle])
        return middle;
}

У моей функции есть указанный прототип (это означает, что у нее есть заданное количество аргументов, которые нельзя изменить), это то, что я имею до сих пор

bool search(int value, int array[], int n) {
    if (array[n/2] == value)
        return 1; 
    else if (array[n/2] < value)
        return search(value, &array[n/2], (n)/2);
    else
        // how do I "return" the other half?
}

Моя реализация пока выглядит правильно? Кажется, я не могу понять, как реализовать окончательное утверждение else.

Answer 1

максимум и минимум представляют границы подмассива, в котором продолжаются исследования.Если вы проанализируете код, то заметите, что если target меньше a[middle], вам придется продолжить исследование в первой половине массива (фактически он вызывает binary_search, проходящий ту же нижнюю границу, новерхняя граница, фактическая middle -1).С другой стороны, если target больше a[middle], вам придется продолжить исследование во второй половине массива (от middle + 1 до high).Конечно, если target равно a[middle], вы закончили.

Answer 2

Хитрость в написании рекурсивного чего-либо:

1. Выясните, как оно должно заканчиваться.
2. Выясните, как оно должно выглядеть за шаг до конца.
3. Выясните, как он должен выглядеть за два шага до его окончания, и как переход от №2 к №1 точно такой же, как переход от №3 к №2.

Шаг № 1:

Если число в начале диапазона поиска - это желаемое число, вернуть true.

Если конец диапазона поиска совпадает с началом диапазона поиска, а число вдиапазон поиска не является требуемым числом, верните false.

Шаг № 2:

Если диапазон поиска имеет длину два, разбейте его на два диапазона поиска одного элемента и выполните поискдиапазон, который может содержать требуемое число.

Шаг № 3:

Если диапазон поиска имеет длину более двух, разделите его на два примерно равных диапазона поиска и найдите диапазон, которыйможет содержать требуемый номер.

(который объединяетэти два будут выглядеть следующим образом)

Если диапазон поиска имеет длину двух или более элементов, разбейте его на два примерно равных диапазона, проверьте наибольшее (последнее) число в «нижнем» диапазоне, есличисло равно или меньше этого числа, поиск в нижнем диапазоне;в противном случае ищите более высокий диапазон.

Этот метод не даст вам оптимального решения, если вы не выберете оптимальный способ решения проблемы;однако, он вернет вам правильное решение (при условии, что вы не совершите никаких грубых ошибок).

Теперь код

bool search(int value int array[], int lowIndex, int highIndex) {
  if (array[lowIndex] == value) {
    return true;
  } else if (lowIndex == highIndex) {
    return false;
  }
  int middleIndex = lowIndex + highIndex / 2;
  if (array[middleIndex] <= value) {
     return search(value, array, lowIndex, middleIndex);
  } else {
     return search(value, array, middleIndex+1, highIndex);
  }
}

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

Answer 3

int * binSearch (int *arr,int size, int num2Search)
{

    if(size==1)
        return ((*arr==num2Search)?(arr):(NULL));

    if(*(arr+(size/2))<num2Search)
        return binSearch(arr+(size/2)+1,(size/2),num2Search);

    if(*(arr+(size/2))==num2Search)
        return (arr+(size/2));

    return binSearch(arr,(size/2),num2Search);
}

Answer 4

Я попытался решить вашу проблему, и приведенный ниже код действительно работает.Но каково условие, чтобы избежать рекурсии, если значение, которое нужно искать, не лежит в массиве

if(value==a[size/2]) return size/2;

    if( value<a[size/2]) {
        search(a,size/2,value);
    } else if (value>a[size/2] && a[size/2]<a[(a.length-1)/2]) {
        search(a,size/2+size,value);
    } else {
        search(a,size/2+a.length-1,value);
    }

Answer 5

return search(value, &array[(n)/2], (n)/2);

В вашем текущем коде, прежде всего, n не должно быть в скобках (это не имеет значения, но меня смущает).

Далее, если он должен возвращать индекс в массиве, ваш код этого не делает, он возвращает 1. Судя по прототипу, вы могли бы рассмотреть нерекурсивный подход, но он может работать нормально, если вы добавляете правильные значения к каждому возврату.

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

       new array if > n/2
         v-----------v
0, 1, 2, 3, 4, 5, 6, 7
         ^
        n/2

На самом деле, вы, вероятно, не хотите включать свое среднее значение. Наконец, не забудьте принять во внимание списки длины ноль, один, два и три. И, пожалуйста, напишите модульные тесты. Это, вероятно, один из наиболее часто неправильно реализованных алгоритмов.

Answer 6

High и low - верхняя и нижняя границы на индексы-кандидаты массива.Другими словами, они определяют часть подмассива, в которой возможно существование цели поиска.Поскольку размер подмассива уменьшается на половину каждой итерации, легко увидеть, что алгоритм равен O (log n).

Answer 7

Переменные high и low представляют текущий диапазон, который вы ищете.Обычно вы начинаете с начала и конца массива, а затем определяете, находится ли значение в первой или второй половине или точно в середине.Если это посередине, вы возвращаете эту точку.Если он ниже середины, вы ищете снова (рекурсивно), но теперь только в нижней половине.Если он выше среднего, вы ищите верхнюю половину.И вы повторяете это, каждый раз разделяя и сужая диапазон.Если вы найдете значение, которое вы вернете, в противном случае, если диапазон настолько узок, что он пуст (и индексы нижнего и верхнего значения одинаковы), вы не нашли его.