配列部分がソートされた部分であると仮定すると、特定の要素を見つける方法はありますか？

Question

正直言って、これはインタビューの質問でした。配列が完全にソートされていれば、バイナリ検索（O（logN））を使うことができます。しかし、現在の状態は次のとおりです。

1. 一部の部分はソートされていますが、他の部分はソートされていません。
2. 私たちは、どの部分がソートされているのか、この部分の長さがわからない。

私はO（N）である完全アレイスキャンソリューションしか考えられませんでした。しかし、インタビュアーによると、O（logN）ソリューションがあるという。助けてください。

Answer 1

面接官が間違っています。ソートされた部分の開始位置とサイズを知らなくても、O（logN）で検索することはできません。

Answer 2

完全な質問をしていないか、インタビュアーが完全に間違っていますか。ここにあなたの説明に合った例があります。

[1, 2, 3, 4, 5, 9, -1, 8, 0, 8, -2, 4, 7, 6]

あなたは最初の5つの要素がソートされて見ての通り。しかし、それは6が私の配列のどこにあるのかを見つけるためにあなたを助けません。あなたはまだ要素を見つけるためにO（n）が必要です。

あなたの質問を極限に置くと、ソートされた部分が2つの要素で構成され、ソートされていない部分がn-2要素の場合はどうなりますか？彼はまだO(log n)でそれを検索できますか？

あなたに助言してください。あなたが実際に信じることができないものを聞いたら、あなたにアイデアを説明し、このアイデアを役に立たない反例を考えてみてください。