バイナリ検索へのイントロ

概要

バイナリ検索は、技術的なインタビューのために、あなたのプロジェクトに遭遇する可能性のある問題の検索に使用するために学ぶ重要な検索アルゴリズムです.大きな配列では、このアルゴリズムは非常に速い.唯一のキャッチは、それがソートされた配列で行うことができるということです.

電話帳アナロジー
多くの人々は、彼らがバイナリ検索について考えるとき、電話帳で検索することを考えたいです.この類推は、ほとんどの人は、単に自分の携帯電話でこれらの日の連絡先を検索を考慮して少しアンティークですが、しかしそれは良い方法は、概念を理解することだと思います.
あなたが電話帳で最後の名前を調べることであったならば、スミスと言う名前を言わせてください、あなたはどうしますか?ほとんどの人は最初に、彼らが名前がそうであるかもしれないと思ったところにフリップします.その後、彼らは彼らが反転ページに名前を確認します.あなたは、Pの前にSの前に来るので、今すぐ電話帳の後ろ半分をチェックする必要があります知っている.したがって、あなたはスミスがそのページにないことを知っているので、あなたが上にあるページ過去まで、最初から電話帳のすべての名前を排除することができます.

あなたが電話帳の残りの部分を介して約半分の場所を検索し、あなたが検索している名前を持つページを見つけるまで、このプロセスを繰り返すと、あなたのターゲット名、スミスに名前を比較する.
これは、バイナリ検索がどのように動作するかに非常によく似ており、それぞれの要素を1つずつ検索するよりもずっと速いのかを説明します.データがソートされるので、我々は我々の目標値がどこにあるかについてより良い推測をすることができます.

擬似コードの処理

このアルゴリズムの知識によって、我々のアルゴリズムがどのように働くべきかについて、擬似コード上で動作するようになります.目標値を探しています5 配列の[0, 1, 2, 3, 5, 7, 8] .
私たちの関数は、配列で見つけるためにソートされた配列と目標値の2つのパラメータを取るべきです.私たちは、毎回、配列の中央の要素を見て、それを我々の目標と比較することを知っています.もしマッチを見つけられなければ、配列の新しい部分を見る必要があるでしょう.
配列の中央を見つける一つの良い方法は、平均を使用することです.平均を見つけるために、我々は我々が現在調査中である配列の部分の左右の側にポインタを必要とするということを知っています私たちは一緒にポインタを追加し、それらを2つに分割する必要があります.これがそうであるので、私たちは、我々が見ている配列の部分の最も遠い左側、および最も遠い右の位置のインデックスにインデックスを保存します.
次に、ループを作成し、マッチを見つけるまで、配列の異なる部分を見続けることができます.各ループを使用して、我々が見ている配列の中央のインデックスを計算し、そのインデックスの値を目標値に比較します.中央値が目標値に一致する場合は、中間値のインデックスを返します.中央値が我々の目標より少ないならば、我々は現在の中央より上に我々の左のポインタをセットして、配列の現在の範囲の最後の半分を見ます.中央値がターゲットより大きい場合、右のポインターを中央インデックスの下の1つに設定し、現在のスコープの先頭を見ます.次にループを実行します.
配列全体を検索した後にマッチを見つけることができない場合は、- 1を返し、ターゲット値に対してインデックスが見つからないことを示します.
ここにいくつかの擬似コードがあります.

function binarySearch(sortedArray, targetValue) {
  //set leftSide to beginning of array at first
  let leftSide = 0
  //set rightSide to end of array at first so the entire array is in scope
  let rightSide = endOfArray

  while (targetNotFound) {
    // average the left and right pointer to find middle. Will need to round this number to get an integer
    let middle = average(left, right)

    if (targetValue === valueAtMiddleIndex) {
      return middle
    } else if (valueAtMiddleIndex < targetValue) {
      leftSide = middle + 1
    } else if (valueAtMiddleIndex > targetValue) {
      rightSide = middle - 1
    }
  }
  // if target value can't be found in array
  return -1
}

テストケースでコードを歩きましょう.

我々は[0, 1, 2, 3, 5, 7, 8] 探している5

leftSide は0 . rightSide は6 .

第1ループ

middle で初期化3

インデックスの要素3 is 3

Does 3 === 5 ? いいえ、目標より小さいです.

leftSide 現在は= 3 + 1 =4

第2ループ

アレイのこの部分を見ています.[5, 7, 8]

middle 現在は( 4 + 6 )/2 =5

インデックスの要素5 is 7

Does 7 === 5 ? いいえ、それは目標より大きいです.

rightSide 現在は= 1 = 5 =4

第3ループ

さて、この部分だけを見ています.[5]

middle 現在は( 4 + 4 )/2 =4

インデックスの要素4 is 5

Does 5 === 5 . はい!

リターンmiddle は4

動く!

問題
疑似コードに問題がありますか?
あなたがループが特定のケースで永遠に実行することができたと思ったならば、あなたは正しいでしょう.我々の現在のコードで、我々が目標値を見つけるならば、我々はループを止めるだけです、しかし、我々がそれを決して見つけないならば、ループは永遠に続きます.
この回路を短絡する良い方法は、左のポインタが右を過ぎないようにすることです.つまり、配列がチェックするもう一つの値になっていて、その値がターゲットに等しくない場合、ループを終了します.更新された擬似コードは以下の通りです.

function binarySearch(sortedArray, targetValue) {
  //set leftSide to beginning of array at first
  let leftSide = 0
  //set rightSide to end of array at first so the entire array is in scope
  let rightSide = endOfArray

  // exit loop if left pointer goes past rightPointer. I removed the targetNotFound condition since the return statement within the loop already handles this.
  while (leftSide <= rightSide) {
    // average the left and right pointer to find middle. Will need to round this number to get an integer
    let middle = average(left, right)

    if (targetValue === valueAtMiddleIndex) {
      return middle
    } else if (valueAtMiddleIndex < targetValue) {
      leftSide = middle + 1
    } else if (valueAtMiddleIndex > targetValue) {
      rightSide = middle - 1
    }
  }
  // if target value can't be found in array
  return -1
}

のように同じ配列を使用して、擬似コードを通して、新しい目標値を歩きましょう4 .

我々は[0, 1, 2, 3, 5, 7, 8] 探している4

leftSide は0 . rightSide は6 .

第1ループ0 ) <= ライサイド6 ):

middle で初期化3

インデックスの要素3 is 3

Does 3 === 4 ? いいえ、目標より小さいです.

leftSide 現在は= 3 + 1 =4

第2ループ4 ) <= ライサイド6 ):

アレイのこの部分を見ています.[5, 7, 8]

middle 現在は( 4 + 6 )/2 =5

インデックスの要素5 is 7

Does 7 === 4 ? いいえ、それは目標より大きいです.

rightSide 現在は= 1 = 5 =4

第3のループleftside4 ) <= ライサイド4 ):

さて、この部分だけを見ています.[5]

middle 現在は( 4 + 4 )/2 =4

インデックスの要素4 is 5

Does 5 === 4 . いいえ、それは目標より大きいです.

rightSide 現在は= 1 = 4 =3

ループ中にleftside4 ) が<= ライサイド3 )

リターン-1

動く!
この擬似コードは、すでに本物にかなり近いですが、私はあなたの仕事をJavaScriptの機能を取得する前に続行するに挑戦します.あなたが以下の私のコードで覗き見をこそこそしないように、ここではGIFです.

バイナリ検索の実装

JavaScriptを使用したこのアルゴリズムの実装です.

function binarySearch(sortedArr, value){
  let left = 0;
  let right = sortedArr.length - 1;

  // I chose to initialize these variables outside the loop
  let middle;
  // currentElem will be the element that is at the middle index
  let currentElem;

  while (right >= left) {
      // Math.floor() will round the decimal down to the nearest integer
      middle = Math.floor((left + right) / 2)

      currentElem = sortedArr[middle];

      if (currentElem === value) {
          return middle;
      } else if (currentElem < value) {
          left = middle + 1;
      } else if (currentElem > value) {
          right = middle - 1;
      }
  }
  return -1;
}

バイナリ検索のビッグO

ビッグOの最悪の場合の性能はO(log n)であり、非常に高速である.JavaScriptの検索メソッドに組み込まれているほとんどのArray.prototype.includes() , を持っているtime complexity o(n)のために、彼らは線形探索を使用するので.

バイナリ探索は、小さいとみなされない配列のための線形探索よりかなり速いです.配列が小さいなら、それは線形探索より速く実行しないかもしれません.私が見るバイナリ検索の唯一の欠点はデータがソートされなければならないということです.

歓声

お読みありがとうございます.今日は何か新しいことを教えられたらいいなと思います.

資源

JavaScript Algorithms and Data Structures Masterclass by Colt Steele

Time Complexity Chart