0

3 次スプライン補間のアプリケーションを使用して、並べ替えられたデータ配列にバイナリ検索を実装しようとしています。すべての範囲で機能させることができません。たとえば、検索番号 4.4 は、範囲 [4.35-4.57] の下限 4.35 を返す必要があります。4.57 は [4.35-4.57] と [4.57, 4.76) などの両方に存在します。

Sub Binary_Search_of_Array()
Dim SplineRanges() As Variant
Dim Right As Integer
Dim Middle As Integer
Dim Left As Integer
Dim SearchNumber As Variant


SplineRanges = Array(4, 4.35, 4.57, 4.76, 5.26, 5.88)
SearchNumber = 4.4


Right = UBound(SplineRanges)
Left = LBound(SplineRanges)
Do While Left < Right
  Middle = Left + (Right - Left) / 2

  If SplineRanges(Middle) < SearchNumber Then
     Left = Middle + 1
  ElseIf SplineRanges(Middle) > SearchNumber Then
     Right = Middle - 1
  Else
    Left = Middle
    Exit Do
  End If
Loop


  Debug.Print SplineRanges(Left - 1); SearchNumber; SplineRanges(Left) ' Tried many different statements to return the correct bounds.



End Sub
4

2 に答える 2

2

あなたの問題はラインにあります

Right = Middle - 1

そうあるべき

Right = Middle

そうしないと、間隔を閉じすぎたり、速すぎたりします...

于 2013-02-07T00:24:51.047 に答える
1

私はあなたのコードに問題を引き起こしていることを (1 つだけ) 指摘しすぎました。私は全体的なロジックをもう一度見て、次のスニペットを思いつきました - これはより簡単で正しいものです:

Do While Right - Left > 1
  Middle = Left + (Right - Left) / 2

  If SplineRanges(Middle) < SearchNumber Then
    Left = Middle
  Else
    Right = Middle
  End If
Loop

Debug.Print SplineRanges(Left); SearchNumber; SplineRanges(Right)

これを 4.01 から 5.88 までの値の全範囲にわたって 0.01 刻みで実行したところ、全体を通して動作しているように見えます。論理を理解するのは少し簡単です。中間値が高すぎる場合は、下限をその点に調整します。それ以外の場合は、上限を調整します。上限と下限の境界が 1 つだけ離れると、ターゲットは「ブラケット内」になります。小さな整数値を除いて、浮動小数点型は実際にはすべてが等しいわけではないことに注意してください。したがって、「4.57 は [4.35-4.57] と [4.57-4.76] の両方に存在する」という点については注意が必要です。いずれにせよ、スプラインを作成しているとき、スプラインにはすべての素敵な連続導関数があるため、「点のちょうど間違った側」にいるときに近似が崩れることはありません...

于 2013-02-07T03:14:44.487 に答える