c# - BinarySearch 如何在两个邻居之间的数组中找到值？

Question

我有一个排序数组double。目标是在数组中查找索引。其中包含 <= 搜索值的值。

例如，数组包含{0, 5, 12, 34, 100}索引范围为 [0 .. 4] 的数字。

搜索值 = 25。我想得到 index=2 （出现范围在 12 到 34 之间）

我不明白在这种情况下如何运行二进制搜索。

   public class MyComparer : IComparer<double>
    {
        public int Compare(double x, double y)
        {
            //<-------- ???
        }
    }

    public double[] spline_x;

    MyComparer cmpc = new MyComparer();
    int i=Array.BinarySearch(spline_x, x, cmpc);

Answer 1

当二分查找未在数组中找到项时，它返回一个负数，该负数是第一个大于 value 的元素的索引的按位补码。这是您可以使用它来查找范围的方法：

double[] spline_x = { 0D, 5D, 12D, 34D, 100D };
int i = Array.BinarySearch(spline_x, 25);
if (i >= 0)
{
    // your number is in array
}
else
{
    int indexOfNearest = ~i;

    if (indexOfNearest == spline_x.Length)
    {
        // number is greater that last item
    }
    else if (indexOfNearest == 0)
    {
        // number is less than first item
    }
    else
    {
        // number is between (indexOfNearest - 1) and indexOfNearest
    }     
}

Answer 2

不熟悉 C#，但简单的二进制搜索可以解决问题，找到最后一个数字 <= N，这是您所描述的边界。

int find_last(int num, const vector<int>&v, size_t begin, size_t end) {
  if (begin >= end) {
    return -1;
  }
  size_t mid = (begin + end) / 2;
  if (v[mid] > num) {
    // [mid, end) is bigger than num, the boundary is in [begin, mid)
    return find_last(num, v, begin, mid);
  }
  // v[mid] is qualified as <= N, search [mid+1, end) for
  // approaching a better boundary if exists.
  size_t index = find_last(num, v, mid+1, end);
  return (index == -1 ? mid : index);
}