Я добрался до второй половины Школы кода викингов. После 8 недель борьбы с Ruby on Rails и всем, что с ним связано, мы бросаем это (на данный момент) и переходим на JavaScript. Это действительно захватывающе, потому что я чувствую, что многие из моих взаимодействий с веб-сайтами очень ориентированы на JavaScript — контент появляется, перемещается, исчезает, скользит и т. д. И теперь я узнаю, как это происходит. И через неделю, пока я встал на ноги, я начинаю чувствовать себя уверенно, пишу эти интерфейсные сценарии.

В то время как у Rails было много места для творчества с точки зрения реализации, JavaScript и jQuery кажутся еще более подходящими для творческого мышления, потому что вы можете полностью определить, как страница должна выглядеть, двигаться и чувствовать себя. Также очень интересно посмотреть, как разные веб-сайты делают свои страницы интерактивными и какие методы они используют (и комбинируют), чтобы это произошло. jQuery великолепен, но он не предоставляет все уникальные типы движения или реакции, которые могут быть на странице, поэтому мне было очень любопытно посмотреть, где разработчикам приходится комбинировать различные аспекты библиотеки и чистый JavaScript, чтобы получить результаты. они ищут.

Но помимо написания этих интерфейсных скриптов, другой поворот заключается в том, что теперь мы должны решать наш ежедневный алгоритм также с помощью JavaScript. Что… интересно? Мне стало очень комфортно решать алгоритмы с помощью Ruby, особенно учитывая его методы Enumerable, поэтому переход был немного непростым и определенно замедлил меня. Но, с другой стороны, это просто дает мне больше повторений при написании JavaScript, что определенно уменьшает количество синтаксических ошибок, которые я делаю. В любом случае, по алгоритму этой недели!

Алгоритм этой недели взят из Cracking the Coding Interview, действительно отличного ресурса, дающего рекомендации по подготовке к техническим вопросам во время интервью. В книге также есть 150 примеров вопросов, поэтому я подумал, почему бы не попрактиковаться с одним из них. Вот что я выбрал:

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

ПРИМЕР: Найти 5 в массиве (15 16 19 20 25 1 3 4 5 7 10 14)

Ответ: 8 (индекс 5 в массиве)

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

На самом деле, бинарный поиск не был моей первоначальной мыслью. Моя настоящая первоначальная мысль была: «Боже, этот массив действительно похож на собаку, гоняющуюся за своим хвостом». И это изображение на самом деле помогает объяснить, как решить этот алгоритм. Суть в том, что вам нужно выяснить, какая половина массива является наименьшим числом. Или, говоря собачьим языком, вам нужно выяснить, где собака ловит свой хвост.

Таким образом, теперь вы не только пытаетесь увидеть, больше или меньше ваш поисковый запрос, чем средняя точка, вы пытаетесь определить, какая половина массива содержит точку, в которой одна запись является самой большой, а за ней следует самая маленькая. Поэтому, когда вы смотрите на каждую половину, вы вставляете некоторый код, чтобы увидеть, полностью ли отсортирована эта половина, или начальная точка на самом деле ниже конечной точки. Вот как выглядит код полностью (обратите внимание, что я использую две буквы m в слове from, потому что from — защищенное слово в JS):

var findElementIter = function(array, searchNum) {
  var fromm = 0
  var to = array.length - 1
  while (fromm <= to) {
    var midPoint = Math.floor((fromm + to) / 2);
    if (searchNum === array[midPoint]) {
      return midPoint;
    } else if (array[fromm] <= array[midPoint]) {
      if (searchNum > array[midPoint]) {
        fromm = midPoint + 1;
      } else if (searchNum >= array[fromm]) {
        to = midPoint - 1;
      } else {
        fromm = midPoint + 1;
      }
    } else if (searchNum < array[midPoint]) {
      to = midPoint - 1;
    } else if (searchNum <= array[to]) {
      fromm = midPoint + 1;
    } else {
      to = midPoint - 1;
    }
  }
  return false;
}

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

Вот как вы находите число в отсортированном массиве, который был повернут. Просто ищите, где собака ловит свой хвост.

На следующей неделе я покажу вам, как получить флешку из связанного списка.