Javascriptのアルゴリズム-二分探索の説明

新しい問題解決スキルを習得し、コンピュータサイエンスの知識をレベルアップしたい場合は、Scrimbaの無料の1時間コースであるThe Working Developer's Guide toAlgorithmsをご覧ください。これは、コンピュータサイエンスのバックグラウンドがなく、アルゴリズムで考えることを学ぶことでメリットが得られると感じている人のために設計されました。

コースは何をしますか?

このガイドでは、6つの異なるバイナリ検索アルゴリズムを作成する方法について説明します。古典的なScrimbaスタイルでは、途中で多くの課題が含まれるため、ソフトウェア開発者としてのスキルを向上させ、今後のアルゴリズムでより適切に機能するために必要な筋肉の記憶を獲得できます。

あなたは学びます:

  • 二分探索
  • ビッグO表記
  • 命令型コード
  • 再帰
  • 末尾再帰
  • 配列分割
  • 配列ビュー
  • パーティション

各アルゴリズムは、次の3つの段階で学習されます。

  • ウォークスルー:ジョナサンはアルゴリズムを概念的に紹介します。
  • 実装:独自のバージョンのアルゴリズムを作成することで、手を汚します。
  • 解決策:ジョナサンは、比較のために彼の実装を示しています。

前提条件

Javascriptを十分に理解していて、理想的にはすでに開発者として働いているか、Bootcampを卒業している場合は、このコースを最大限に活用できます。

まだそこにいない場合は、Scrimbaのすばらしい無料チュートリアル「JavaScript入門」と「ES6 +入門」をご覧ください。

インストラクターの紹介

Jonathan Lee Martinは、ソフトウェア開発者、Web教育者、講演者、および著者です。彼は、執筆、スピーチ、没入型ブートキャンプ、ワークショップ、オンラインチュートリアルを通じて、他の開発者が専門的および個人的な目標を達成するのを支援しています。

NASAやHPなどの企業を含むクライアントの場合、彼はあなたを学習の旅に連れて行ってくれる人です。それでは始めましょう!

二分探索

SweeperとSplitterの検索のグラフ。

画像をクリックしてコースにアクセスしてください。

最初のキャストで、ジョナサンはBig-O表記法二分探索の概念を紹介します。これは私たちが使用するアルゴリズムです。

Big-O表記は、アルゴリズムの最悪の場合のパフォーマンスを説明する手段です。O(n)のBig Oは、配列の長さがn要素の場合、実行時間はnに比例することを示します。つまり、700万エントリの配列が最悪の場合700万エントリを取得するのと同様に、7エントリの配列は最悪の場合7回のルックアップを実行します。上のグラフに示されているように、このアルゴリズムの実行時間は線形であるとも言えます。

二分探索は、「この要素はリストのどこに表示されますか?」という質問に答えるためのいくつかの戦略の1つです。

質問に答えるとき、2つの主要なアプローチがあります:

  • スイーパー:正しいアイテムが見つかるまで、リスト内の各アイテムをチェックします。
  • スプリッター/バイナリ検索:リストを半分に分割し、アイテムを見つけるのに行き過ぎかどうかを確認し、それぞれ右側または左側を検索して、アイテムが見つかるまで繰り返します。

これらのアプローチは、昔ながらの紙の電話帳をチェックするという観点から考えることができます。スイーパーアプローチでは、最初から正しいエントリが見つかるまで、すべてのエントリを調べます。スプリッターアプローチは、ほとんどの人が使用するアプローチです。本をランダムに開き、エントリが見つかるまで前に進む必要があるか、戻る必要があるかを確認します。

バイナリ検索は、特に大きなリストの場合、スイーパーアプローチよりも効率的です。ただし、リストがすでに並べ替えられている場合にのみ機能します。

スイーパーアプローチには線形ランタイム(上のグラフを参照)とO(n)のBig Oがありますが、スプリッターアプローチにはサブリニアランタイムとO(log n)のBigOがあります。

命令

最初のチャレンジキャストでは、ジョナサンは、固定量のメモリとループを使用して、O(n)のBig Oを使用する従来のスタイルでバイナリ検索を実装することにより、手を汚すことを推奨しています。

Jonathanは、ソリューションが成功することを確認するために使用できるテストスイートを提供し、彼の実装を確認する前に、自分でチャレンジを試すことをお勧めします。ここにはネタバレはありませんので、キャストに行って試してみてください。

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.

今すぐコースに進んで、自分でチャレンジしてみてください。ジョナサンが指摘しているように、この課題は注意が必要です。長い間行き詰まった場合は、彼の解決策にスキップしてもかまいませんが、最初に自分で試してみてください。

要約

あなたはコースの終わりに到達しました-素晴らしい仕事です!二分探索へのいくつかのアプローチをカバーしましたが、すべて独自の長所と短所があり、アルゴリズムを効果的に使用するための優れた筋肉の記憶を構築しました。

二分探索への6つの異なるアプローチを見てきましたが、プログラミングのさまざまな場所でポップアップすることに気付くでしょう。

10個のアルゴリズムを備えたジョナサンのフルコースは年末に公開される予定ですが、それまでの間、新しく見つけたバイナリ検索スキルを有効に活用していただければ幸いです。

ハッピーコーディング:)