LANG SELRCT

コードを書く場所についてはこちら

2017年10月30日月曜日

シート内でキーワードに一致する値を探す(二分探索)

指定した値がシートの何行目にあるのか探したい場合
上から順に見ていく方法を『線形探索』といいますが
今回は探す範囲を半分ずつ絞って
一致する値があればログに出すというコードを書いてみました

この探し方を『二分探索(binary search)』といいます
※探索対象のデータは昇順・降順で順番になっている前提です

線形探索の方法はこちら


例えばこんなシートがあるとして
「s」は何行目にあるのかプログラムでみつけたい

見つけたらこんな感じで探したプロセスをログに出したい


ということを実現するコードです

このプロセスは探す範囲を半分ずつ絞っていくので
まずはaからzの真ん中の位置にあるmを見てmはsよりも小さい(昇順の順番が)ので
次の探索はmより下を見に行き
mからzの範囲の真ん中の位置にあるtはsよりも大きいので
次の探索はtよりも上を見に行くといった感じで
sにたどり着くまで範囲を半分に絞っていきます

コード.gs
function binarysearch() {
  var keyword = "s";
  var ss = SpreadsheetApp.getActiveSpreadsheet();
  var sh = ss.getActiveSheet();
  var range = sh.getRange("A:A");
  range.sort([{column: 1, ascending: true}]);
  var values = range.getValues();
  var head = 0;
  var tail = values.length - 1;
  var index = 0;
  while (head <= tail) {
    var middle = Math.floor((head + tail) / 2);
    Logger.log(values[middle][0])
    if (values[middle][0] == keyword) {
      index = middle;
      break;
    } else if (values[middle][0] < keyword) {
      head = middle + 1;
    } else {
      tail = middle - 1;
    }
  }
  Logger.log(index + 1)
}
意訳.gs
この処理は以下を実行する
キーワードを設定する
現在開いているスプレッドシートを取得する
現在開いているシートを取得する
A:Aの範囲を指定して
A列を昇順にソートして
すべての値を取得する
探索範囲の先頭の初期値を0にして
探索範囲の末尾の初期値はA列の値の個数-1にする
indexの初期値は0にする
先頭の数値が末尾の数値以下である限り
対象範囲の中央にある値を
ログに出し
もしその中央の値が探している値なら
indexに中央の数値を入れて
処理から抜ける
もし中央の値が探している値よりも小さいなら
次に探す範囲の先頭は中央の値の下からにする
それ以外(中央の値が探している値よりも大きい)なら
次に探す範囲の末尾は中央の値のひとつ上にする


ログにキーワードの行数を出す


今回使ったデータ


alphabet
a
b
c
d
e
f
g
h
i
j
k
l
m1回目の探索時の半分の位置にあるmはsよりも小さいので次はmから下を見る↓1
1
n
2
o
p3回目の探索時の半分の位置にあるpはsよりも小さいので次はpから下を見る↓3
3
q
r4回めの探索時の半分の位置にあるrはsよりも小さいので次はrから下を見る↓4
4
s5回目の探索時の半分の位置にあるsが探している値なのでこの行数をログに出す←55
t2回目の探索時の半分の位置にあるtはsよりも大きいので次はtから上を見る↑2
u
v
w
x
y
z