こんにちは。ヤマヤタケシです。
土日に一人GameJamだー！って家にこもってコード書いてましたが、ぜんぜん進まなくて驚きだぜ！
最初に妄想していたときは今頃はリッチなモデルぐりぐり動いているはずだったのに・・・。
自分を過信しすぎているというか、修業が足りません。
あとAmazon Primeは罪深いです。

で、この記事はそんな過程で生まれて副産物です。

C#のListで2分探索またの名をバイナリサーチをやってみました。
やっぱ頭から順番に調べるのってダサいじゃん。
バイナリサーチならO(log n)ですよねー。

今回は、ある距離以上を移動すると「位置と距離」をリストにためます。
そのリストをあとから距離をキーにして、位置も補間したいわけです。
例えばこんなデータです。
distance, position(x, y, z)
0.0, (0.0, 0, 0)
1.5, (1.5, 0, 0)
2.5, (2.5, 0, 0)
—
で、これを 1.0 っていう距離をいれたら、　(1.0, 0, 0) が返ってくるようにしたいと。
で、たくさんのデータがあると線形探索だと遅いのでかっこつけて二分探索しようという感じです。

ちょっと調べたら、ちゃんとListにBinarySearchってのがあるじゃないですか。

しかも、一致すればインデックスが返ってきるし、一致しなくても「負の値。 ビットごとの補数」が返ってくるんですって、うおー便利ー。
え、ごめん、ちょっと言ってることわからない。
え？一致しないときは何が返ってくるって？
ビットごとの補数ってなんすか？

ということで、テストしてみました。

//
// BinarySearchのテスト
//
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class BinarySearchTest : MonoBehaviour
{
    List<float> list = new List<float>(new[] { 0.0f, 1.0f, 2.0f, 3.0f } );
    void Awake()
    {
        Test(-1);
        Test(0);
        Test(0.5f);
        Test(1.0f);
        Test(1.5f);
        Test(2.0f);
        Test(2.1f);
        Test(3.0f);
        Test(3.5f);
    }
    void Test(float value)
    {
        var index = list.BinarySearch(value);
        if( index < 0 )
        {
            index = ~index;
        }
        Debug.LogFormat( "{0} -> {1}", value, index);
    }
}

-1 -> 0
0 -> 0
0.5 -> 1
1 -> 1
1.5 -> 2
2 -> 2
2.1 -> 3
3 -> 3
3.5 -> 4

補数っていうのが普段あんまり使わないのだけれど、1の補数と2の補数があるらしく、ビットを反転するのは1の補数になるらしい。
2の補数は1の補数+1ね。
そういうわけで、上記のコードではチルダ”~”っていう3年に1回しか使わないようなビット反転演算子を、マイナスのときに使ってログを出しています。
そうするとうまい具合に次の数のインデックスになってくれました！
いえーい。
なかなかクセのある実装ですが、ちゃんと理解すれば便利です。
最初意味わからなくて自作しようかと思いましたが、思いとどまりました。

補数については「2の補数を理解する (1)Add Star」を参考にしました。

そんじゃまた。