Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
1
Help us understand the problem. What is going on with this article?
@aa_debdeb

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

More than 1 year has passed since last update.

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

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


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

1
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
aa_debdeb
Engineer, Creative Coder。Dentsu Craft Tokyo所属。

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
1
Help us understand the problem. What is going on with this article?