どうも自分のアルゴリズムの理解があいまいっぽい。オーバービューでとらえる癖があるので、バイナリサーチもオーバービューでとらえられていない。最初から持っているイメージは、ソートされた配列があり、ターゲットの場所を特定したり、なかった場合は、挿入されるべき場所のインデックスを返す場合どのようにサーチするか？というものだが、自分は当初は、次のように考えていた。
- Sorted Array の中央値を探す。Start, End の値と比較して、ターゲットが、右にあれば、Startを中央値に、そうでなければ、Endを中央値に、ずばりの値であれば、それを返却。
みたいなイメージで理解していた。ところが、このイメージで問題を解くと、解けるのは解けるのだが面倒くさいことになった。少なくともテストはパスするが、頭がごっちゃになったし、正解まで相当ミスをした。自分的にパターンを網羅して条件分岐を書いたのだが、条件分岐が複雑で網羅するにはどうしたらいいか、あってるのか？などは全く確信がなかった。単にエラーで返ってくるから条件を追加するといった感じだ。
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それ自体は既に検査ずみなので、その左、右となりから、次のループを始めておくと、かなりすっきり書くことができる。
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が解答。
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が解答なので、ブレークするようにしている。
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でカバーしてきたけど、このあたりに強くなる方法をしりたいな。