I have a task from my professor and I need to search through an ordered array using BinarySearch and find the indexes of all values in a given interval. My current approach to the problem is to find the lowest value that fits the requirements take its index then the same for the highest values and after that just take all indexes between these two. This approach should work because the array is ordered in ascending order. My problem is that I cannot get the function that finds the lower bound to work.
For the problem. Instead of getting the lower boundary, I get -1 so the algorithm gets all indexes from -1 to the upper boundary. Our professor doesn't care if we implement the algorithm ourselves as long as we can defend it and understand it in front of him. The program runs fine but gives the wrong result. Instead of giving me the actual indexes that contain all values that fit inside this interval, it gives me all indexes from -1 to the upper bound.
My task is: I have an array of temperatures and I need to write an algorithm which when given an interval will return all indexes that contain values that are inside this interval. The margin for errors is 0.9, which means that if my interval is [20...25] 19.1 is ok but 19 isn't by the same logic 25.9 is ok but 26 is not.
Here is my code:
static void Main(string[] args)
{
Random rnd = new Random();
double[] arrNumber = new double[90000000];
for (int i = 0; i < arrNumber.Length; i++)
arrNumber[i] = rnd.NextDouble() * 1000;
Array.Sort(arrNumber);
double[] interval = { 200, 250 };
var time = Stopwatch.StartNew();
int[] index = ExtractInterval(arrNumber, interval);
time.Stop();
TimeSpan timeTaken = time.Elapsed;
Console.WriteLine(timeTaken);
Console.WriteLine(index.Length);
Console.WriteLine(arrNumber[index[0] - 1]);
Console.WriteLine(arrNumber[index.Length]);
Console.ReadLine();
}
static int[] ExtractInterval(double[] arrNumber, double[] interval)
{
double start = interval[0];
double end = interval[1];
List<int> result = new List<int>();
int lowerBound = findLowerBound(arrNumber, start);
int upperBound = findUpperBound(arrNumber, end);
for (int i = lowerBound; i < upperBound; i++)
{
result.Add(i);
}
return result.ToArray();
}
static int findLowerBound(double[] arr, double lowerBound)
{
int low = 0;
int high = arr.Length - 1;
while(low <= high)
{
int middle = low + (high - low) / 2;
if(Math.Abs(arr[middle] - lowerBound) > 0.9)
{
high = middle - 1;
continue;
}
if (Math.Abs(arr[middle] - lowerBound) < 0.9)
{
if (Math.Abs(arr[middle - 1] - lowerBound) < 0.9)
{
low = middle - 1;
continue;
}
return middle;
}
}
return -1;
}
static int findUpperBound(double[] arr, double upperBound)
{
int low = 0;
int high = arr.Length - 1;
while (low <= high)
{
int middle = low + (high - low) / 2;
if (Math.Abs(arr[middle] - upperBound) > 0.9)
{
high = middle - 1;
continue;
}
else if (Math.Abs(arr[middle] - upperBound) < 0.9)
{
if (Math.Abs(arr[middle + 1] - upperBound) < 0.9)
{
low = middle + 1;
continue;
}
else
{
return middle;
}
}
}
return -1;
}
If you are free to use framework methods, do not implement binary search yourself. Use Array.BinarySearch. Do note you may need to read thru the description of the return value a few times to understand it:
The index of the specified value in the specified array, if value is found; otherwise, a negative number. If value is not found and value is less than one or more elements in array, the negative number returned is the bitwise complement of the index of the first element that is larger than value. If value is not found and value is greater than all elements in array, the negative number returned is the bitwise complement of (the index of the last element plus 1). If this method is called with a non-sorted array, the return value can be incorrect and a negative number could be returned, even if value is present in array.
So we need to consider all cases
var lowerIndex = Array.BinarySearch(arrNumber, lowerBound)
if(lowerIndex >= 0){
// Exact match
}
else{
lowerIndex = ~lowerIndex; // ~ means "bitwise complement"
if(lowerIndex < arrNumber.Length){
// found index of value next larger than lowerBound
}
else {
// lowerBound larger than all items
}
}
The upper bound would look similar, but you need to subtract 1 to get all valid temperatures, and you need to check if the resulting index is still larger than zero.
To ensure you find the first/last item in case of multiple exact matches you can can use custom comparers, these essentially guarantees that you never get to the "exact match" case, and instead find the first, or next larger item.
class LowerComparer : IComparer<double>
{
public int Compare(double x, double y) => x < y ? -1 : 1 ;
}
class UpperComparer : IComparer<double>
{
public int Compare(double x, double y) => x <= y ? -1 : 1;
}
From here it should be fairly straightforward to do the same for both the lower and upper bound and construct the range. But pay attention to the indices, it is very easy to get of-by-one errors in code like this.
If you have a tolerance, just apply this to the bounds before searching. So [20...25] would turn into [19.1 ... 25.9].
I would also recommend to test your code with a few arrays that are short enough that you can step thru the code. Pay special attention to edge cases or error cases: