二进制搜索(Spline应用程序)

Question

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

Answer 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“的观点是很棘手的。无论如何，当你制作样条曲线时，当你“只是在一个点的错误一侧”时，近似不会崩溃，因为样条曲线有所有那些可爱的连续导数……

Answer 2

你的问题出在队伍里

Right = Middle - 1

那应该是

Right = Middle

否则，您将关闭间隔太远，太快...