JavaScript: поиск в массивах JavaScript с помощью двоичного поиска

function binarySearch(value, list) {
  // ваш код
}

 var myArray = [1, 2, 3, 5, 6, 7, 10, 11, 14, 15, 17, 19, 20, 22, 23];
 document.writeln(binarySearch(6, myArray)); // 4

Двоичный поиск

Предположим, что вам нужно угадать число. Вас попросят угадать число от 1 до 100. Если ваше число слишком большое или слишком маленькое, вы получите подсказку. Вы хотите угадать за минимальное количество попыток. Поэтому лучше начать угадывать с 50. Если искомое число больше, то вы можете дальше назвать число 75. Если оно меньше, то это означает, что число находится в диапазоне от 50 до 75, и вы выбрали бы число, которое находится в середине. Вы будете продолжать в таком стиле, пока не угадаете число. Подобный образом работает бинарный поиск.

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

Для поиска 9 в списке: 1 2 3 4 5 6 7 8 9 10

Сначала мы находим средний элемент. Это элемент в позиции Math.floor((first + last)/2), где first - первый индекс, а last - последний индекс. Мы выбираем округление так, чтобы в случае, если результат является дробью, он становится целым числом. Средний элемент в этом списке равен 5. Наше поисковое значение 9 больше 5, поэтому мы ищем список:

6 7 8 9 10

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

9 10

Средний элемент равен 9, поэтому мы можем остановить наш поиск здесь.