JavaScriptで重複のあるソート済み配列から指定した値の範囲をバイナリサーチで取得する

ソート済み配列から指定した値を持つインデックスの範囲をバイナリサーチで取得する方法です。

binarysearchMinIndexは重複要素があるソート済み配列arrayから指定した値targetを持つ最も小さいインデックスを取得する関数です。引数のfromとtoはサーチする配列の範囲を指定します。binarysearchMaxIndexはbinarysearchMinIndexとは逆に指定した値を持つ最も大きいインデックスを取得する関数です。
binarysearchRangeが目的のソート済み配列arrayから指定した値targetを持つインデックスの範囲を取得する関数です。内部ではbinarysearchMinIndexとbinarysearchMaxIndexを使用しています。

function binarysearchMinIndex(array, target, from, to) {
  while (from !== to) {
    const middle = from + Math.floor((to - from) / 2);
    if (array[middle] < target) {
      from = middle + 1;
    } else {
      to = middle;
    }
  }
  if (array[from] === target) {
    return from;
  } else {
    return -1;
  }
}

function binarysearchMaxIndex(array, target, from, to) {
  while (from !== to) {
    const middle = from + Math.ceil((to - from) / 2);
    if (array[middle] > target) {
      to = middle - 1;
    } else {
      from = middle;
    }
  }
  if (array[from] === target) {
    return from;
  } else {
    return -1;
  }
}

function binarysearchRange(array, target) {
  const from = binarysearchMinIndex(array, target, 0, array.length - 1);
  const to = from !== -1 ? binarysearchMaxIndex(array, target, from, array.length - 1) : -1;
  return { from: from, to: to };
}

---

通常のバイナリサーチのコードも載せておきます。重複要素のないソート済み配列arrayから指定した値targetのインデックスを取得します。もし指定した値の要素がない場合は-1を返します。

function binarysearch(array, target) {
  let from = 0;
  let to = array.length - 1;
  while (from <= to) {
    const middle = from + Math.floor((to - from) / 2);
    if (array[middle] < target) {
      from = middle + 1;
    } else if (array[middle] > target) {
      to = middle - 1;
    } else {
      return middle;
    }
  }
  return -1;
}

今回は目的のbinarysearchRange関数をその値を持つ最も小さなインデックスと最も大きなインデックスをそれぞれバイナリサーチで見つけるような実装をしました。同じ値を持つ要素が少ないことが分かっている場合、通常のバイナリサーチでその値を持つインデックスを見つけてからその前後を線形探索で調べるというアルゴリズムもあります。

---

ソースコードをgistに置いておきました。
https://gist.github.com/aadebdeb/964ff754d4045e2b7b1fea8044e7420d