search - セットの最大値を見つける

Question

数値がある点まで増加し、その後減少する数値のリストがある場合、その最大値を見つけるために作成しなければならないセットのサイズに関係なく、有限数の推測がありますか?

値間の距離は任意であり、増加側の値の数は減少側の値の数と異なる場合があります。

最良の方法は何ですか？要素 1 をチェックし、次に最後の要素をチェックし、次にその中間の要素をチェックしますか? そして繰り返しますか？それとももっと洗練されたものですか？

このようなアルゴリズムの処理時間はどれくらいになるでしょうか?

Answer 1

1 つの要素の代わりに 2 つの隣接する要素を固定値と比較するバイナリ検索を使用できます。a := 0、b := n、i := (a+b)/2 から開始し、要素 (i) と要素 (i+1) を比較します。e(i+1) > e(i) に気付いた場合、ブレークポイントが i の後のどこかにあることがわかっているので、a := i を設定します。e(i) < e(i-1) の場合はその逆で、b := i を設定します。

その場合、複雑度は O(log n) になります。より多くの比較が必要なため、通常のバイナリ検索よりも少し遅くなります。

Answer 2

リスト内の要素の数に基づいて、順序付き検索に似た再帰アルゴリズムを試すことができます。

擬似コード:

List search(int index, List listpart){
   if(listpart.length()==1){ // already found
       return listpart
   }
   else if(listpart(index+1)>listpart(i) && listpart(index-1)<listpart(i)){ //search right part
      List listpart_tmp = getlistpart(listpart, index, listpart.length())
      return search(index+(listpart.length()/4), listpart_tmp
   }
   else if(listpart(index+1)<listpart(i) && listpart(index-1)>listpart(i)){ //search left part
      List listpart_tmp = getlistpart(listpart, 0, index)
      return search(index-(listpart.length()/4), listpart_tmp
   }
   else if(listpart(index+1)<listpart(i) && listpart(index-1)<listpart(i)){ //found 
      return getlistpart(listpart, index, index)
   }
}

関数

getlistpart

指定されたインデックス間の元のリストの要素で構成されるリストを返す関数です。