C＃与えられた範囲ごとに関数を計算する

Question

O（n）を実行しないで、与えられた範囲から最小値を求める必要があります。

配列は、対角線または双曲線である可能性があります。ここでは3つのサンプルの配列です：

var arrDiag1 = new double[10] { 0, 0.5, 1, 1.5, 2, 2.5, 3, 3.5, 4, 4.5 }; 
var arrDiag2 = new double[10] { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }; 
var arrHyperbole = new double[10] { 9, 8, 7, 6, 5, 4, 3, 4, 5, 6 }; 

私は砂漠の演習でラインからの計算のいくつかの並べ替えを構築しようとしたが、それには良いが出てきません。 誰か良いアイデアがありますか？ではなく第二と第三で、それが動作する最初の配列で

private double BinarySearchMin(double[] arr, int left, int leftMiddle, int rightMiddle, int right) 
    { 
     if (left == right) 
      return arr[left]; 

     if (arr[leftMiddle] < arr[rightMiddle]) 
     { 
      right = rightMiddle; 
      leftMiddle = ((right - left)/3); 
      rightMiddle = ((right - left)/3 * 2); 
      return BinarySearchMin(arr, left, leftMiddle, rightMiddle, right); 
     } 
     if (arr[leftMiddle] > arr[rightMiddle]) 
     { 
      left = leftMiddle; 
      leftMiddle = ((right - left)/3) + left; 
      rightMiddle = ((right - left)/3 * 2) + left; 
      return BinarySearchMin(arr, left, leftMiddle, rightMiddle, right); 
     } 
     if (arr[leftMiddle] == arr[rightMiddle]) 
     { 
      left = leftMiddle; 
      right = rightMiddle; 
      leftMiddle = ((right - left)/3) + left; 
      rightMiddle = ((right - left)/3 * 2) + left; 
      return BinarySearchMin(arr, left, leftMiddle, rightMiddle, right); 
     } 
     return -1; 
    } 

：dasblinkenlightの助けを借りて助け

更新

ため

おかげで私はこの方法を得ることができましたアレイ。 私はここで何が欠けていますか？

Answer 1

機能が一つだけ最小値を有する場合、Ternary Searchを使用する：

3分探索アルゴリズムは、単峰関数の最小値または最大値を求める手法です。

アイデアは、3つの等しいセグメント範囲を分割し2つの検索点でプローブし、次いでないが最小を含有しないもの「にプル」することです。探索点に間隔の左側にi1を仮定し、そしてi2右側：

• F [I1]場合< F [I2]、次いで最小値は0とI2との間にあります。右から引き込む
• f [i1]> f [i2]の場合、最小値はi1とNの間です。
• f [i1] == f [i2]の場合、最小値はi1とi2の間です。両側から引き込みます。

アルゴリズムの実行時間はO（log N）です。

Answer 2

私は通常、宿題に関する質問に答えるのが嫌いですが、私はこれにいくらか似ています。

まず、2つの「対角線」の場合は何も特別なものではなく、最小限がエッジにあるような誇張についての別の見方を考えてください。

次に、最小値を見つけるためにバイナリ検索のようなものを試してください。 2つの中間要素を見て、それらの関係を見て、最小限になる側を決定してください。要素が1つだけ残るまで繰り返します。