BinarySearch, how to find value in array between two neighbors?
I have a sorted double array . The goal is to find the index in the array. Which contains value <= search value.
For example, an array contains numbers {0, 5, 12, 34, 100}
with a range of indices [0 .. 4].
Find value = 25. And I want to get index = 2 (occurrence range from 12 to 34)
I don't understand how the binary search would be done in this case.
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);
+3
source to share
2 answers
When binary search finds no element in the array, it returns a negative number that is the bit's complement to the index of the first element that is greater than the value. This is how you can use it to find a range:
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
}
}
+12
source to share
Not familiar with C #, but a naive binary search does the trick, finding the last number <= N, which is the boundary you described.
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);
}
0
source to share