Алгоритми в Javascript - Обяснено двоично търсене

Ако искате да придобиете нови умения за решаване на проблеми и да повишите знанията си по компютърни науки, не търсете повече от безплатния едночасов курс на Scrimba, The Working Developer's Guide to Algorithms. Той е предназначен за тези, които нямат опит в компютърните науки и смятат, че биха се възползвали от това да се научат да мислят алгоритмично.

Какво прави курсът?

Нашето ръководство ще ви отведе как да създадете шест различни бинарни алгоритми за търсене. В класическия стил Scrimba той съдържа куп предизвикателства по пътя, така че ще спечелите мускулната памет, необходима ви, за да подобрите уменията си като разработчик на софтуер и да работите по-добре с алгоритмите напред.

Ще научите:

  • Двоично търсене
  • Голяма O нотация
  • Императивен код
  • Рекурсия
  • Рекурсия на опашката
  • Разделяне на масива
  • Изглед на масив
  • Преграда

Всеки алгоритъм се преподава на три етапа:

  • Упътване: Джонатан въвежда алгоритъма концептуално.
  • Внедряване: Зацапваме ръцете си, като създаваме собствени версии на алгоритъма.
  • Решение: Джонатан ни показва своето изпълнение за сравнение.

Предпоставки

Ще извлечете максимума от този курс, ако разбирате добре Javascript и в идеалния случай вече работите като разработчик или сте завършил Bootcamp.

Ако все още не сте там, разгледайте страхотните безплатни уроци на Scrimba Въведение в JavaScript и Въведение в ES6 +.

Въведение в инструктора

Джонатан Лий Мартин е разработчик на софтуер, уеб педагог, лектор и автор. Той помага на други разработчици да постигнат своите професионални и лични цели чрез писане, говорене, завладяващи Bootcamps, семинари и онлайн уроци.

С клиенти, включително компании като NASA и HP, той е просто човекът, който ще ви преведе през учебното пътуване. Така че нека да започнем!

Двоично търсене

Графика на търсенето на Sweeper срещу Splitter.

Щракнете върху изображението за достъп до курса.

В първия актьорски състав Джонатан запознава с понятията Big-O нотация и двоично търсене , алгоритъма, с който ще работим.

Нотацията Big-O е средство за описание на най-лошия случай на изпълнение на алгоритъм. Голямото O на O (n) казва, че ако масив има дължина от n елемента, времето за изпълнение ще бъде пропорционално на n. С други думи, масив от седем записа ще отнеме 7 търсения в най-лошия случай, точно както масив от 7 милиона записа ще вземе 7 милиона записа в най-лошия случай. Също така можем да кажем, че времето на изпълнение на този алгоритъм е линейно, както е показано на графиката по-горе.

Бинарното търсене е една от няколкото стратегии за отговор на въпроса "Къде се появява този елемент в списък?"

Когато отговаряте на въпроса, има два основни подхода:

  • Sweeper : Проверка на всеки елемент от списъка, докато се намери правилния елемент.
  • Splitter / Binary Search : Разделяне на списъка на половина, проверка дали сте отишли твърде далеч или не достатъчно далеч, за да намерите елемента, търсене или отляво или отдясно съответно и повтаря, докато се намира на елемента.

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

Бинарното търсене е по-ефективно от подхода за почистване, особено за по-големи списъци. Но работи само когато списъкът вече е сортиран.

Докато подходът за почистване има линейно време на изпълнение (вижте графиката по-горе) и Big O на O (n), подходът на разделителя има подлинейно време на изпълнение и Big O на O (log n).

Наложително

В първото предизвикателство, Джонатан ни насърчава да си изцапаме ръцете, като внедря двоично търсене в традиционен стил, т.е.

Джонатан ни предоставя тестов пакет, който можем да използваме, за да сме сигурни, че нашето решение е успешно и ни насърчава да опитаме сами предизвикателството, преди да проверим неговото изпълнение. Тук няма спойлери, затова се отправете към актьорския състав, за да опитате сами.

While this solution is short and close to the original formulation of binary search, you've probably noticed that the solution was difficult to write and not the best solution from a software craftsmanship point of view. Read on to find out ways to level up the solution...

Recursion

In this cast, we look at improving our binary search by implementing a new version with a few constraints. While our solution should still have a Big O of O(n), it should not use loops and must use recursion. All variables should be initialized with the const operator so they can't be mutated.

Jonanthan kicks us off with a skeleton version of the solution and then encourages us to try the challenge on our own:

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

If you've completed this challenge, you've probably seen that this solution is a lot easier to read but is quite verbose. In the worst case, it can also result in infinite recursion. Continue with the course to see whether there are ways of streamlining the solution...

Tail Recursion

The challenge for the next cast is to improve our previous implementation by reducing duplication.

Jonathan warns us that the solution will look worse than the previous two solutions, however, it sets us up for some better optimizations further down the line. Head over to the course now to try the challenge for yourself and see Jonathan's solution.

Array Splitting

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 алгоритми, ще излезе в края на годината, но междувременно се надявам да можете да използвате добре своите новооткрити бинарни умения за търсене.

Приятно кодиране :)