#はじめに
先日、みんな大好きエナジードリンクのZONeより、'mad_hacker'; Ver1.0.0が発売されました。
何というネーミングでしょうか。マッドハッカー...
早速買ってみたところ、何やら缶にプログラムがデザインされていました。
かっこいい！！これは実行してみたい...！
#コード入力
何はともあれ、まずは写経です。
だまってコードを打ち込みます。
缶という円柱に描かれただけでも読みにくいのに、改行もない、他のデザインにコードが邪魔されてる、文字色も見えにくいですが、とにかくカッコいいので頑張って読み取ります。
全部で缶に30行ほどのコードがありますが、4行半ばまででひとつの関数が終わってるぽいので、今回はそこまで。
何やらJavascript という言語らしいです。
経験がない言語ですが、何となく改行しながら書きます。
function binarySearch(arr, val, min, max){
if (max < min) {
return false;
}
const half = Math.floor(min + (max - min) / 2);
if(arr[half] === val){
return half;
}
return arr[half] > val ? binarySearch(arr, val, min, half - 1) : binarySearch(arr, val, half + 1, max);
}
binarySearch（二分探索）
関数名から察するに、これは二分探索アルゴリズムです。
ソート済の配列やリストの中から、特定の値を見つけるアルゴリズムですね。
Wikipedia様の例を参考に、値を入れてみます。
下記のような配列から25を探しだすことを考える。
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|データ | 1 | 3 | 5 | 11 | 12 | 13 | 17 | 22 | 25 | 28|
// 配列作成
search_list = [1,3,5,11,12,13,17,22,25,28]
// 関数実行
ans = binarySearch(search_list, 25, 0, search_list.length);
// 結果確認
console.log(ans);
第一引数に探索対象配列のsearch_listを、第二引数に探索対象である25を渡します。
第三、第四引数のminとmaxは探索対象の数値ではなく、配列の要素数を渡してあげるようです。
minには0、maxにはsearch_list.lengthで取得した配列の要素数（=10）を渡します。
実行結果
Javascript は未経験で環境もないため、今回はpaiza.ioでJavascript を実行しました。
8
ここでもう一度例題を見てみましょう。
下記のような配列から25を探しだすことを考える。
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|データ | 1 | 3 | 5 | 11 | 12 | 13 | 17 | 22 | 25 | 28|
この25という数字が配列のどの位置にあるか探索するのが二分探索でした。
位置としては9番目ですが、配列は0始まりなので、8で正解ですね！
#まとめ
グレープソーダのようで美味しかったです。
ZONe 'mad_hacker'; にはソートされた配列から任意の値を取り出す二分探索がコーディングされていました。
ハッカー関係あるのでしょうか？
しかし何にせよ、Javascript 未経験だったので良い勉強になりました。
残りの30行もどうやら探索アルゴリズム系っぽいです。気になりますね。
AtCoderと連携しているみたいです。
続きは気が向いたら。