Задача алгоритмов Академии Хана: двоичный поиск

Ниже приведен простой код двоичного поиска, написанный на JS. Этот код возвращает -1, тогда как он должен возвращать 20. Что я сделал, немного осмотревшись:

  1. Замена «пока (мин ‹ макс)» на «пока (мин ‹ = макс)» приведет к появлению ошибки в KhanAcademy.

  2. Я использовал функцию Math.floor, которая по какой-то причине выдает ошибку «env.Math.floor не является функцией», поэтому вместо этого использовал «Math.round».

    var doSearch = function(array, targetValue) {
      var min = 0;
      var max = array.length - 1;
      var guess;
      while (min < max) {
        guess = Math.round((max + min) / 2);
        if (array[guess] === targetValue) {
          return guess;
        } else if (array[guess] < targetValue) {
          min = guess + 1;
        } else {
          max = guess - 1;
        }
      }
      return -1;
    };
    var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];
    var result = doSearch(primes, 73);
    console.log("Found prime at index " + result);
     //print (primes[]);
     //Program.assertEqual(doSearch(primes, 73), 20);


javascript algorithm binary-search khan-academy
person desicoder    schedule 12.10.2016    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Предлагаю изменить значение min rps max на guess при присвоении новых значений.

Дополнительно предлагаю поменять Math.round на Math.floor.

(Небольшой совет: после возврата предложение if закончилось, поэтому else if не нужно.)

var doSearch = function (array, targetValue) {
    var min = 0;
    var max = array.length - 1;
    var guess;
    while (min < max) {
        guess = Math.floor((max + min) / 2);
        if (array[guess] === targetValue) {
            return guess;
        }
        if (array[guess] < targetValue) {
            min = guess;
        } else {
            max = guess;
        }
    }
    return -1;
};
var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97],
    result = doSearch(primes, 73);

console.log("Found prime at index " + result);

person Nina Scholz    schedule 12.10.2016
comment
Да! Спасибо, что указали на эту небольшую ошибку, код действительно дает ожидаемый результат, но я все еще получаю сообщение об ошибке, говорящее, что у вас почти правильное условие в цикле while, но с ним все еще что-то не так. на KhanAcademy - person desicoder; 12.10.2016
comment
1. Пусть мин = 0 и макс = n-1. 2. Если max ‹ min, то стоп: цель отсутствует в массиве. Возврат -1. 3. Вычислите предположение как среднее значение максимального и минимального значений, округленное в меньшую сторону (чтобы оно было целым числом). 4. Если массив[догадка] равен цели, то останавливаемся. Ты нашел это! Вернуть предположение. 5. Если догадка была слишком низкой, то есть массив[догадка] ‹ цель, тогда установите min = догадка + 1. 6. В противном случае догадка была слишком высокой. Установите максимальное значение = предположение - 1. 7. Вернитесь к шагу 2. - person desicoder; 12.10.2016

arrow_upward
0
arrow_downward

Это в минимальном и максимальном расчете. Сигналы «+» и «-» меняются местами.

    var doSearch = function(array, targetValue) {
      var min = 0;
      var max = array.length - 1;
      var guess;
      while (min < max) {
        guess = Math.round((max + min) / 2);
        if (array[guess] === targetValue) {
          return guess;
        } else if (array[guess] < targetValue) {
          min = guess - 1;
        } else {
          max = guess + 1;
        }
      }
      return -1;
    };
    var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];
    var result = doSearch(primes, 73);
    console.log("Found prime at index " + result);
     //print (primes[]);
     //Program.assertEqual(doSearch(primes, 73), 20);

person Andre Canilho    schedule 12.10.2016
comment
Вызов Академии Хана: двоичный поиск Это мой вызов, я все еще, кажется, получаю сообщение об ошибке. - person desicoder; 13.10.2016

arrow_upward
0
arrow_downward

в вашем коде просто небольшая ошибка. Вы должны изменить мин = предположение + 1 на мин = предположение - 1.

    var doSearch = function(array, targetValue) {
      var min = 0;
      var max = array.length - 1;
      var guess;
      while (min < max) {
        guess = Math.round((max + min) / 2);
        if (array[guess] === targetValue) {
          return guess;
        } else if (array[guess] < targetValue) {
          min = guess - 1;
        } else {
          max = guess + 1;
        }
      }
      return -1;
    };
    var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];
    var result = doSearch(primes, 73);
    console.log("Found prime at index " + result);
     //print (primes[]);
     //Program.assertEqual(doSearch(primes, 73), 20);

person Lourenço Biselli    schedule 12.10.2016
comment
ссылка Это мой вызов, я все еще, кажется, получаю сообщение об ошибке. - person desicoder; 13.10.2016