Алгоритми в Javascript - пояснення двійкового пошуку

Якщо ви хочете набути нових навичок вирішення проблем та покращити свої знання з інформатики, не дивіться далі на безкоштовний одногодинний курс Скрімби «Робочий посібник розробника з алгоритмів». Він був розроблений для тих, хто не має досвіду комп’ютерних наук і вважає, що їм було б корисно навчитися мислити алгоритмічно.

Що робить курс?

Наш путівник проведе вас через те, як створити шість різних алгоритмів двійкового пошуку. У класичному стилі Scrimba він містить купу викликів на цьому шляху, тому ви отримаєте м’язову пам’ять, необхідну для вдосконалення своїх навичок розробника програмного забезпечення та кращої роботи з алгоритмами.

Ви дізнаєтесь:

  • Двійковий пошук
  • Великі позначення O
  • Імперативний код
  • Рекурсія
  • Рекурсія хвоста
  • Розбиття масиву
  • Вид масиву
  • Перегородка

Кожен алгоритм викладається у три етапи:

  • Покрокове керівництво: Джонатан вводить алгоритм концептуально.
  • Впровадження: Ми забруднюємо руки, створюючи власні версії алгоритму.
  • Рішення: Джонатан показує нам його реалізацію для порівняння.

Передумови

Ви отримаєте максимум від цього курсу, якщо добре розумієтесь на Javascript і в ідеалі вже працюєте розробником або випускником Bootcamp.

Якщо ви ще не там, перегляньте чудові безкоштовні підручники Scrimba Вступ до JavaScript та Вступ до ES6 +.

Вступ до викладача

Джонатан Лі Мартін - розробник програмного забезпечення, веб-педагог, спікер та автор. Він допомагає іншим розробникам досягти своїх професійних та особистих цілей завдяки написанню, розмові, захоплюючим Bootcamps, майстер-класам та онлайн-підручникам.

З клієнтами, включаючи такі компанії, як NASA та HP, він просто той, хто проведе вас через навчальний шлях. Тож давайте почнемо!

Двійковий пошук

Графік пошуку Sweeper проти Splitter.

Клацніть на зображення, щоб отримати доступ до курсу.

У першому складі Джонатан знайомить з поняттями нотації Big-O та двійкового пошуку , алгоритмом, з яким ми будемо працювати.

Позначення Big-O - це засіб опису найгіршої роботи алгоритму. Велике O з O (n) говорить, що якщо масив має довжину з n елементів, час виконання буде пропорційний n. Іншими словами, масив із семи записів займе 7 пошуків у найгіршому випадку, як і масив із 7 мільйонів записів займе 7 мільйонів записів у гіршому випадку. Ми також можемо сказати, що час виконання цього алгоритму є лінійним, як показано на графіку вище.

Бінарний пошук - одна з кількох стратегій для відповіді на питання "Де цей елемент відображається у списку?"

Відповідаючи на питання, існує два основних підходи:

  • Підмітальна машина : Перегляд кожного елемента у списку, поки не буде знайдено правильний предмет.
  • Розділювач / двійковий пошук : Розбиття списку навпіл, перевірка того, зайшли Ви занадто далеко чи недостатньо далеко, щоб знайти елемент, здійснюючи пошук відповідно правої чи лівої сторони та повторюючи, поки елемент не буде знайдений.

Ми можемо думати про ці підходи як про перевірку паперової телефонної книги старої школи. Підхід до підмітальної машини передбачав би перегляд кожного і кожного входу з самого початку, поки не буде знайдено правильний. Більшість людей застосовують спліттер - відкриваючи книгу випадковим чином і перевіряючи, чи потрібно їхати вперед чи назад, поки запис не буде знайдений.

Бінарний пошук є більш ефективним, ніж підмітальний підхід, особливо для більших списків. Але це працює лише тоді, коли список уже відсортований.

У той час як підмітальний підхід має лінійний час виконання (див. Графік вище) та Великий O з O (n), роздільний підхід має підлінійний час виконання та Великий O з O (log n).

Імператив

У першому складі виклику Джонатан закликає нас забруднити руки, реалізуючи двійковий пошук у традиційному стилі, тобто з великим O з O (n), використовуючи фіксовану кількість пам'яті та циклів.

Джонатан надає нам набір тестів, який ми можемо використовувати для забезпечення успішності нашого рішення, і закликає нас спробувати завдання самостійно, перш ніж перевірити його реалізацію. Тут немає спойлерів, тож вирушайте до акторського складу, щоб спробувати самі.

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

Рекурсія

У цьому складі ми розглядаємо вдосконалення нашого двійкового пошуку шляхом впровадження нової версії з кількома обмеженнями. Хоча наше рішення все одно повинно мати великий O з O (n), воно не повинно використовувати цикли і повинно використовувати рекурсію. Усі змінні слід ініціалізувати за допомогою constоператора, щоб їх не можна було мутувати.

Джонантан запускає нам каркасну версію рішення, а потім заохочує спробувати самостійно:

let binarySearchWithRecursion = (array, element, compare = defaultCompare) => { return -1; }; export default binarySearchWithRecursion; 

Якщо ви виконали цей виклик, ви, мабуть, переконалися, що це рішення набагато легше для читання, але досить багатослівне. У гіршому випадку це також може призвести до нескінченної рекурсії. Продовжуйте курс, щоб побачити, чи існують способи впорядкування рішення ...

Рекурсія хвоста

Завданням для наступного складу є вдосконалення попередньої реалізації за рахунок зменшення дублювання.

Джонатан попереджає нас, що рішення буде виглядати гірше, ніж попередні два рішення, однак, воно налаштовує нас на кращі оптимізації далі. Зараз перейдіть на курс, щоб спробувати виклик для себе і побачити рішення Джонатана.

Розбиття масиву

If you completed the previous challenge, you may have felt that we're still passing a lot of extra information into our binary search via recursion. This cast looks at a way of cleaning that up called array splitting.

We can think of array splitting in terms of our phone book example from earlier - whenever we decide that half the phone book is irrelevant, we just tear it off and throw it away. Similarly, our next solution should disregard any parts of the array which don't include our desired entry.

To help us achieve this, Jonathan starts us off with some skeleton code:

let binarySearchWithArraySplitting = ( array, element, compare = defaultCompare ) => { return -1; }; 

Then, as usual, he gives us free rein to try to the solution for ourselves before walking us through his own implementation.

Although this is an elegant method of binary search, because it involves making a copy of part of the array, it no longer has a Big O of O(n) and has a higher memory usage and slower run time. Continue with the course to find out whether there is a way to regain a higher performance with a similar code solution...

Array View

In this cast, we look for ways of merging the higher performance of our previous solutions with the elegance of array splitting. To do this, we create an array-like object that responds to the same methods as an array. We'll then inject this object in place of the original array.

Jonathan gets us started by initializing a function ArrayView which returns an object that expects three arguments: array, start and end. When invoked, ArrayView should return an object with four methods, length, toArray, slice and get.

export let ArrayView = ( array, start = 0, end = array.length, ) => ({ length: end - start, toArray: () => array.slice(start, end), slice: () => , get: () => , }); let binarySearchWithArrayView = (array, ...args) => binarySearchWithArraySplitting(ArrayView(array), ...args) 

Our challenge is to implement the slice and get methods of ArrayView without making a copy of the original array. Click through to try it out and then view Jonathan's walkthrough.

Although this solution produces better, more readable code, it is longer than some of our previous solutions. Continue with the course to find out if we can retain the benefits of ArrayView while lifting even more of the logic out of binary search code...

Array Partition

In the final challenge cast of the course, Jonathan gives us a goal of extracting some of the cryptic bounce logic in our previous version into a data structure.

For this, we need a simple data structure which returns the middle, left or right part of an array. To start us off, Jonathan sets up a function ArrayPartition:

export let ArrayPartition = (array, pivot) => ({ left: () => array.slice(0, pivot), middle: () => array.get(pivot), right: () => array.slice(pivot + 1, array.length), }); 

Next, Jonathan sets up a new version of binary search called binarySearchWithPartition, which has a starting signature the same as binarySearchWithArraySplitting:

let binarySearchWithPartition = (array, element, compare = defaultCompare) => { if (array.length === 0) { return -1; } const middle = Math.floor(array.length / 2); const comparison = compare(element, array.get(middle)); if (comparison === 0) { return middle; } //bounce logic const [left, right] = comparison === -1 ? [0, middle - 1] : [middle + 1, array.length]; //end of bounce logic const subIndex = binarySearchWithArraySplitting( array.slice(left, right), element, compare ); return subIndex === -1 ? -1 : left + subIndex; }; let binarySearchWithPartitionAndView = (array, ...args) => binarySearchWithPartition(ArrayView(array), ...args); 

Our challenge now is to rewrite binarySearchWithPartition with none of the bounce logic highlighted above, instead of creating an array partition and making calls to its left, middle and right methods.

Перейдіть на курс зараз, щоб спробувати завдання самостійно. Як зазначає Джонатан, цей виклик складний, тому можна переходити до його рішення, якщо ви застрягли занадто довго, але спробуйте спочатку самостійно.

Підсумовування

Ви пройшли курс до кінця - чудова робота! Ми розглянули декілька підходів до двійкового пошуку, усі з яких мають власні переваги та недоліки, і створили чудову м’язову пам’ять для ефективної роботи з алгоритмами.

Тепер, коли ви побачили шість різних підходів до двійкового пошуку, ви, мабуть, помітите, що він з’являється в багатьох різних місцях програмування.

Повний курс Джонатана з 10 алгоритмами вийде в кінці року, але тим часом, сподіваюся, ви зможете добре використати свої знайдені навички двійкового пошуку.

Щасливого кодування :)