Binary Search アルゴリズム

どうも自分のアルゴリズムの理解があいまいっぽい。オーバービューでとらえる癖があるので、バイナリサーチもオーバービューでとらえられていない。最初から持っているイメージは、ソートされた配列があり、ターゲットの場所を特定したり、なかった場合は、挿入されるべき場所のインデックスを返す場合どのようにサーチするか？というものだが、自分は当初は、次のように考えていた。

* Sorted Array の中央値を探す。Start, End の値と比較して、ターゲットが、右にあれば、Startを中央値に、そうでなければ、Endを中央値に、ずばりの値であれば、それを返却。

みたいなイメージで理解していた。ところが、このイメージで問題を解くと、解けるのは解けるのだが面倒くさいことになった。少なくともテストはパスするが、頭がごっちゃになったし、正解まで相当ミスをした。自分的にパターンを網羅して条件分岐を書いたのだが、条件分岐が複雑で網羅するにはどうしたらいいか、あってるのか？などは全く確信がなかった。単にエラーで返ってくるから条件を追加するといった感じだ。

```C#
public class Solution
{
        public int SearchInsert(int[] nums, int target)
        {
            var minIndex = 0;
            var min = nums[0];

            if (nums.Length == 0) return 0;
            var maxIndex = nums.Length - 1;

            var max = nums[maxIndex];
            if (min >= target) return 0;
            if (max == target) return nums.Length - 1;
            if (max < target) return nums.Length;
            while (true)
            {
                var midIndex = (maxIndex - minIndex) / 2 + minIndex;
                if (nums[midIndex] == target) return midIndex;

                if ((nums[minIndex] < target && target < nums[midIndex]) && ((midIndex - minIndex) == 1)) return midIndex;
                if ((nums[midIndex] < target && target < nums[maxIndex]) && ((maxIndex - midIndex) == 1)) return maxIndex;

                if (nums[midIndex] > target)
                {
                    maxIndex = midIndex;
                }
                else
                {
                    minIndex = midIndex;
                }
                if (minIndex == maxIndex) return maxIndex;
            }

        }
}
```
# 何が間違っていたのか？

この解き方は何が間違っていたのだろうか？条件分岐の整理が悪い？多分違う。自分の考えではバイナリサーチを十分理解してなかったというのが、今の想定だ。私はバイナリサーチを

> Sorted Array の中央値を探す。Start, End の値と比較して、ターゲットが、右にあれば、Startを中央値に、そうでなければ、Endを中央値に、ずばりの値であれば、それを返却。

ととらえていたのだが、もう少し細かいところまで含めてパターンになっているのではと気が付いた。

* 最初のIndexをLeft, 最後のIndex をRightとして、中央値を　Pivotとする
* Pivotの値がターゲットなら、Pivotのポインタを返却
* Pivotの値がターゲットより大きいなら、Right = pivot - 1
* Pivotの値がターゲットより小さいなら、Left = pivot + 1
* LeftとRightの大小関係が入れ替わったら、Left のインデックスの値がターゲットの値

ここまで含めてパターンになっている。例えば私のふわっとした書き方だと、Pivotの値を含んで次のループに行くので無限ループが発生しうるし、境界値問題もクソめんどくさいことになってしまった。しかし、ここまでパターンだと思うと、入れ替わりでブレーク、Pivotそれ自体は既に検査ずみなので、その左、右となりから、次のループを始めておくと、かなりすっきり書くことができる。

```C#
        public int SearchInsert(int[] nums, int target)
        {
            int left = 0, pivot = 0;
            int right = nums.Length - 1;
            while (left <= right)
            {
                pivot = (right - left) / 2 + left;
                if (target == nums[pivot]) return pivot;
                if (target < nums[pivot]) { right = pivot - 1; } else
                {
                    left = pivot + 1;
                }
            }
            return left;
        }
```

相当すっきりする。これだと、人間の頭でも条件分岐が、ずばりの値、より小さい、より大きいなので、困ることがない。
ちゃんと理解できたかどうかわからないので、もう一問やってみよう。次はローテーションされたSortedArrayの最小値を求める問題。

`[4 5 6 1 2 3]` のなかから、最小値を求める問題。上記のパータンに当てはめてアルゴリズムを考える。

* Left, Right, Pivot (中央値) を求める
* Pivot と Right を比較して、Rightのほうが小さいなら、右側に答えがあるので、Left = Pivot + 1
* そうではければ、Right = Pivot - 1
* Left とRight が入れ替わったらブレークして、Leftが解答。

```C#
        public int FindMin(int[] nums)
        {
            int left = 0, pivot = 0;
            int right = nums.Length - 1;
            while(left < right)
            {
                pivot = (right - left) / 2 + left;
                
                if (nums[pivot] > nums[right])
                {
                    left = pivot + 1;
                } else
                {
                    right = pivot - 1;
                }
            }
            return nums[left]; 
        }
```

ところが、上記の条件だけでは、うまくいかない、パターンの中で忘れているものがある。Pivotがそのものずばりのケースだ。
`[5 6 7 1 2 3 4]` このパターンだと最初のループでいきなり最小値を検出できてしまっているが、それが最小値と知りうるすべがないどうするべきか？
　そこでこう考えてみた。このまのロジックでいくと、right = pivot - 1 で、`nums[right] > nums[pivot]` になる。本来、`nums[right]`は`nums[pivot]`よりも元の定義で行くと小さくなってしかるべきなのに、ここのロジックに来たはずなのに、実際逆になる。これが、Pivotが解答になっているケースの判別式になる。あと、もう一つ考慮するべきは、Index ouf of range で、例えば　`[1 2]` みたいなものだとすると、L=0, P=0, R=1 で上記の計算でいくと、nums[pivot] < nums[right] なので、right = pivot -1 になる。ただし、このケースだと、right = -1になってしまうので、レンジあふれを考慮して、レンジあふれのケースを考慮し、その場合ははやりLeftが解答なので、ブレークするようにしている。

```C#
        public int FindMin(int[] nums)
        {
            int left = 0, pivot = 0;
            int right = nums.Length - 1;
            while(left < right)
            {
                pivot = (right - left) / 2 + left;
                
                if (nums[pivot] > nums[right])
                {
                    left = pivot + 1;
                } else
                {
                    right = pivot - 1;
                    if (right < 0 || nums[right] > nums[pivot])
                    {
                        left = pivot;
                        break;
                    }
                }
            }
            return nums[left]; 
        }
```

# まとめ
バイナリサーチの原本にあたったわけではないので、どこまでがパターンかは正確にはしらないが、このレベルまでをパターンと考えると、いろいろすっきり解けることに気が付いたので、自分のためにメモしておいた。昔から条件分岐のパターンを考えるのは苦手で、TDDでカバーしてきたけど、このあたりに強くなる方法をしりたいな。