0

我一直在尝试使用三次样条插值的应用程序对已排序的数据数组实现二进制搜索。我无法让它在所有范围内运行。例如，搜索编号 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

我太快地指出（仅）一件让你的代码有问题的事情。我再次查看了所有逻辑，并提出了以下代码段 - 这更容易理解和更正：

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)

我以 0.01 的步长在 4.01 到 5.88 的整个值范围内运行它，它似乎始终表现得很好。逻辑更容易理解：如果你的中点值太高，那么你将你的下边界调整到那个点；否则你调整你的上限。一旦上下边界仅相距一，您的目标就“在括号中”。请注意，除了小整数值之外，浮点类型并不是真的每个都达到相等。因此，您关于“4.57 存在于 [4.35-4.57] 和 [4.57-4.76] 中”的观点很棘手。无论如何，当你制作样条曲线时，当你“只是一个点的错误的一面”时，近似值不会崩溃，因为样条曲线有所有那些可爱的连续导数......

于 2013-02-07T03:14:44.487 回答