もうすぐデータ構造のクラスで試験を受けます。準備として、Web で見つけたアルゴリズムに基づく問題を調べていて、得られないように見える問題に遭遇しました。
部屋に入ると、n 枚のカードが並んでいるのが見えます。それぞれに番号 xi が書かれており、i は 1 から n の範囲です。ただし、最初はすべてのカードが裏向きになっています。あなたの目標は、ローカル ミニマムを見つけることです。つまり、カード i の数が隣接するカードの数以下である xi-1 >= xi <= xi+1 です。最初と最後のカードも極小値になる可能性があり、比較する隣接カードは 1 つだけです。明らかに多くの極小値が存在する可能性がありますが、そのうちの 1 つを見つける責任があるだけです。
私が思い付くことができる唯一の解決策は、基本的にそれらをすべてひっくり返し、極小値を見つけることです。ただし、課題は、O(logn) カードをめくるだけでこれを行うことです。
基本的に、カード「7」が表示されている場合、左側のカードが「10」で右側のカードが「9」の場合、極小値です。これは、ログイン時にどのように簡単に行うことができますか?
助けていただければ幸いです。