【JavaScript】配列の要素を二分探索で抽出してみた

二分探索のメリット

線形探索よりも短い時間でターゲットを見つけることができる。

コード

// arr ソート済みの配列
// target 見つけたい要素
function binarySearch(arr, target) {
    let idx = null;
    let iMin = 0;
    let iMax = arr.length - 1;
    while (iMin <= iMax) {
      let iMid = Math.floor((iMin + iMax) / 2);
      if (arr[iMid] === target) {
        idx = iMid;
        break;
      } else if (arr[iMid] < target) {
        iMin = iMid + 1;
      } else {
        iMax = iMid - 1;
      }
    }
    
    return idx;
  }

初期値（idx）をnullにすることで、配列の要素に正の数、負の数混じっていても抽出することができるようになりました。この関数終了時にidxに値が代入されていれば、要素発見となります。idxにnullが代入されている場合は探索したい要素が配列に存在しなかったことになります、

参考文献(コードをお借りしました)

• JavaScriptによる2分探索(バイナリサーチ) のサンプルコード
  https://tech-blog.s-yoshiki.com/entry/195