数値やアルファベットの二分探索と同じ方法では日本語の探索がうまくいかなかったため、今回は日本語を二分探索する方法を書いていこうと思います
方法としては
- 日本語を数値に変換して
- その数値を昇順でソートして
- 二分探索を行う
関連する記事
コード.gsfunction binarysearch() {
var keyword = "東京都";
var keyword_code = parseInt(get_char_code(keyword));
var ss = SpreadsheetApp.getActiveSpreadsheet();
var sh = ss.getActiveSheet();
var range = sh.getRange("A2:A");
var values = range.getValues();
for (var i = 0; i < values.length; i++) {
var text = values[i][0];
var code = parseInt(get_char_code(text));
sh.getRange((i + 2), 2).setValue(code)
}
var sort_range = sh.getRange("A2:B");
sort_range.sort([{
column: 2,
ascending: true
}]);
var code_range = sh.getRange("B2:B");
var code_values = code_range.getDisplayValues();
var head = 0;
var tail = code_values.length - 1;
var row = 0;
while (head <= tail) {
var middle = Math.floor((head + tail) / 2);
row = middle + 2;
if (parseInt(code_values[middle][0]) == keyword_code) {
break;
} else if (parseInt(code_values[middle][0]) < keyword_code) {
Logger.log([row + "行目" + values[middle][0] + "より大きい"]);
head = middle + 1;
} else {
Logger.log([row + "行目" + values[middle][0] + "より小さい"]);
tail = middle - 1;
}
}
Logger.log(keyword + "は " + (row) + "行目です")
}
function get_char_code(text) {
var code_array = [];
for (var i = 0; i < text.length; i++) {
code_array.push(text[i].charCodeAt());
}
var keyword_code = code_array.toString().replace(/,/g, "");
return keyword_code;
}
| 意訳.gsこの処理は以下を実行する 探したいテキストを指定して それをget_char_codeで処理して数値に変換する 現在開いているスプレッドシートの 開いているシートの A2:Aの範囲の 値をすべて取得して 値の数だけ以下の処理を繰り返す textに値を入れて それをget_char_codeで処理して数値に変換する ２つめの列（つまりB列）に入力する A2:Bの範囲を取得し 以下設定でソートする 基準の列は2（つまり数値の入っているB列） 昇順にする B2:Bの範囲を取得して 表示されている値をすべて取得する 探索範囲の先頭の初期値を0にして 探索範囲の末尾の初期値はA列の値の個数-1にする rowの初期値は0にする 先頭の数値が末尾の数値以下である限り 対象範囲の中央の値を取得し 行数はその値に+2したもの（code_values[0][0]はB2の値なので行数には+2する必要がある） もしその中央の値が探している値なら 処理から抜ける もし中央の値が探している値よりも小さいなら 探している値は中央よりも大きい方にあるとログに出す 次に探す範囲の先頭は中央の値の下からにする それ以外（中央の値が探している値よりも大きい）なら 探している値は中央よりも小さい方にあるとログに出す 次に探す範囲の末尾は中央の値のひとつ上にする 最終的に見つけた行数をログに出す この処理は以下を実行する code_arrayという入れ物を用意して textの文字数だけ以下の処理を繰り返す code_arrayにtextの一文字ずつを数値変換した値を追加していく code_arrayを文字列に変換してカンマを削除した値をkeyword_codeに入れて 返す |
試してみる
例としてこんなシートを用意して
上記コード.gsのbinarysearch()を実行すると
各都道府県名を数値変換したものがB列に入力されて
B列が昇順でソートされます
そしてこの中から「東京都」が何行目にあるのかを二分探索で見つけるプロセスと結果がログに出ます
