JavaScript Interview Coding Test Problem 6

Изучите два различных способа завершения поиска в отсортированном массиве. Мы рассмотрим метод грубой силы и более элегантный метод.
Поиск в отсортированном массиве
Инструкции
Напишите функцию, которая принимает отсортированный массив целых чисел и число. Возвращает индекс этого числа, если он есть. Функция должна возвращать -1 для целевых значений, отсутствующих в массиве.
Входные данные: **Массив целых чисел, целое число
**Выход: **Целое число от -1 и далее.
**Решение 1

1   function search(numbers, target) {
2     for(let i = 0; i < numbers.length; i++) {
3       if(numbers[i] === target) {
4         return i;
5       }
6     }
7
8     return -1;
9   }
Войдите в полноэкранный режим Выйти из полноэкранного режима

Это решение очень простое. Мы проходим через массив и пытаемся найти нашу цель.
Время
Поскольку мы проходим через весь массив, временная сложность составляет: O(n).
Пространство
Поскольку мы храним заданное количество переменных, пространственная сложность составляет: 0(1).
Бинарный поиск
Мы можем найти лучшее решение. Поскольку массив отсортирован, мы можем прыгать по массиву, пока не найдем нужный индекс.
Поиск слова
Представьте, что вы ищете слово в словаре. Будет ли эффективно перебирать все слова, пока мы не найдем нужное? Нет, это было бы ужасно неэффективно.
Лучшим подходом будет открыть словарь наполовину. Если наше слово находится в алфавитном порядке перед словами на средней странице, мы знаем, что наше слово находится в первой половине книги.
Затем мы можем пролистать ~1/4 пути по словарю. Снова повторив вышеописанный процесс, мы можем исключить еще половину оставшихся страниц.
Мы можем повторять вышеописанные действия снова и снова, пока не найдем слово. Это гарантирует, что даже если словарь огромен, мы сможем найти наше слово гораздо быстрее, чем если бы мы просматривали каждое слово по отдельности.
Масштабирование
На самом деле, если мы удвоим размер словаря, добавив в него больше слов, нам придется повторить этот процесс еще раз. Это не намного больше работы, даже если словарь станет намного толще.
Давайте воплотим этот подход в коде.
Решение 2

1   function binarySearch(numbers, target) {
2     let startindex = 0;
3     let endindex = numbers.length - 1;
4
5     if(target < numbers[startindex] || target > numbers[endindex]) {
6       return -1;
7     }
8
9       while(true) {
10    if(numbers[startindex] === target) {
11      return startindex:
12      }
13
14      if(numbers[endindex] === target) {
15        return endindex; }
17
18  if(endindex - startindex <= l) {
19  //indicates the number isn't present
20  return -1;
22
23  const middleindex = Math.floor((startindex + endindex)/2);
24
25      if(target > numbers[middlelndex]) {
26        Startindex = middlelndex + 1;
27      } else if(target < numbers[middlelndex]) {
28        endindex = middleindex - 1;
29      } else {
30        return middlelndex;
31      }
Войти в полноэкранный режим Выйти из полноэкранного режима

Как это работает
Мы начинаем с проверки того, что цель находится в радиусе действия массива, в противном случае возвращается
false в противном случае.

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

Оцените статью
devanswers.ru
Добавить комментарий