Looking for any tips on how to speed up/rewrite the following function. The array is ordered so was thinking could this be replaced with BinarySearch but as I need to return the nearest indexes it might not be appropriate.

For the purpose of this investigation assume istart = 0 and iend = Array Length -1

/// <summary>
    /// Given an array "xx" of length "n", and given a value "x", this routine
    /// returns a value "j" such that "x" is between xx(j) and xx(j 1).  
    /// xx must be monotonic, either increasing or decreasing.  j=istart or j=n is
    /// returned to indicate that x is out of range.
    /// Modified to set the start and end points by "istart" and "iend" 
    /// </summary>
    public static int Locate(double[] xx, int n, int istart, int iend, double x)
    {

        if (istart > iend || x < xx[istart])
        {
            return istart;
        }
        else if (x > xx[iend])
        {
            return iend;
        }

        int mid;
        while (istart  1 < iend)
        {
            mid = (istart   iend) >> 1;
            
            if (x < xx[mid])
            {
                iend = mid ;
            }
            else
            {
                istart = mid ;
            }
        }

        if (iend >= n || xx[iend] != x)
        {
            return iend -1;
        }
        else 
            return iend;


    }

CodePudding user response：

See Array.BinarySearch

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 you should be able to replace your function with

var index = Array.BinarySearch(xx, istart, iend - istart   1, x);
if(index < 0){
   index = ~index -1 // take the bitwise complement and subtract one to get the index of the value before x

Note that you might need to do some additional checks for cases like empty arrays, or if x is smaller or larger than all values, since it looks like some specific output is required for such cases.

such that "x" is between xx(j) and xx(j 1)

The 'between' is a bit ambiguous here since it does not specify if the range is inclusive or not. You kind of have to assume it is inclusive, since x would not be part of the non-inclusive set x to x n.

Also note that the parameters are kind of weird, The length is not needed, since arrays know they own length. And when specifying intervals of arrays you usually use index length, and not start end, since there may be some confusion if you should include the end-index or not.

As a last point, whenever dealing with performance, measure. Benchmark.net is the gold standard, but a stopwatch might do in a pinch. A profiler is also helpful to hint at where the problem might be.