Вопросы Теги

Бинарный поиск с использованием рекурсии, принимая только искомое значение в параметре

Это не уникально для jQuery, но является аспектом javascript. Все функции - это объекты. Например ::

var f = function() { alert('yo'); }
f.foo = "bar";

alert(f.foo); // alerts "bar"
f();          // alerts "yo"
0
задан Nicholas Tower 17 January 2019 в 16:52
поделиться

1 ответ

Необходимо передать обновленные l и u в качестве параметров рекурсивному методу. То, что вы делаете, это присваиваете одинаковые значения l (= 0) и u (= n-1) в каждом вызове. Другими словами, каждый рекурсивный вызов не решает проблему меньшего размера . Это та же самая проблема и, следовательно, она приводит к переполнению стека.

Вот псевдокод. 

int binarySearch(int v, int l, int u) {
    if (l <= u) {
       find mid
       is the element at mid:
           return 1;// Can be 'mid' to return the index at which it was found.
       should we go left:
           return binarySearch(v, l, mid - 1);
       should we go right:
           return binarySearch(v, mid + 1, u);
    } 
    return -1; //Not found
}

. Обратите внимание:

  1. Базовое условие (l <= u). Это позволит нам обнаружить состояние отсутствующего элемента и завершить рекурсию.
  2. Ключевое слово return в каждом рекурсивном вызове, без которого вы всегда будете возвращать -1.

ОБНОВЛЕНИЕ:

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

int binarySearch(int v) {
    if (l <= u) {
       find mid
       is the element at mid:
           return 1;// Can be 'mid' to return the index at which it was found.
       should we go left:
           u = mid - 1
           return binarySearch(v);
       should we go right: 
           l = mid + 1
           return binarySearch(v);
    } 
    return -1; //Not found
}

Примечание. Перед вызовом этого метода необходимо установить l = 0 и u = n - 1.

0
ответ дан user7 17 January 2019 в 16:52
поделиться
Другие вопросы по тегам:

Похожие вопросы: