バイナリ検索での悪いケースのシナリオについて

Question

バイナリ検索の悪いケースは1 + lg nですが、要素がソートされた配列にある場合、または要素がそれに含まれていない場合、この悪化するケースが変わりますか？要素が配列内にないと判断するための検索が少なくてすむと思っていますか？または検索が同じになっていますか？

Answer 1

最悪の場合はkの比較を行う必要があります要素が配列内にあります。最後（kth）の比較では、キーが一致しない場合、要素は明らかに配列内にありません。したがって、kthの比較の後で要素が配列内にない場合、これ以上の比較を行う必要はありません。

したがって、ソートされた配列内の要素に関係なく、最悪の場合は、k=ceil(log(n))に変わりません。

同様に、線形検索の場合、キーが配列の最後の場所にあるとします。 nの比較が必要であり、配列の最後の要素がキーと一致しない場合、要素が配列内にないと判断できます。これ以上の比較は必要ありませんし、配列に存在する要素に関係なく最悪の場合は同じ（n）になります。