BinarySearch如何找到兩個鄰居之間的數組值？

Question

我有一個排序陣列雙。 目標是在數組中找到索引。 其中包含值< =搜索值。

例如，該數組包含索引範圍[0..4]的數字{0, 5, 12, 34, 100}。

搜索值= 25。我想要索引= 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

當二進制搜索沒有找到在數組項，它返回一個負數，其是比值大的第一個元素的索引的按位求補。這裏是你可以用它來尋找範圍的方式：

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); 
}