Find Range of a number from an array.

Question

I'm just rephrasing the question I asked a little while ago. I have a sorted array {2.0,7.8,9.0,10.5,12.3}

If I given an input 9.5 What is the fastest way to find 9.0 and 10.5 to indicate that 9.5 is in between 9.0 and 10.5 (9.5 >=9.0 and <10.5) ? Is binary search an option?But since the input need not be in the array.I'm not sure how I should do this.

Also If there is any other data structure that is suitable please comment.

Answer 1

I would do it like that

double valuebefore = 0;
            double valueafter = 0;
            double comparevalue = 9;
            foreach (var item in a)
            {
                valueafter = item;
                if (item > comparevalue)
                {
                    break;
                }
                valuebefore = item;
            }

            System.Console.WriteLine("Befor = {0} After = {1}", valuebefore, valueafter);

Answer 2

A binary search would certainly be the "standard" approach - http://en.wikipedia.org/wiki/Binary_search_algorithm. Speed is O(log(N)) as opposed to linear.

In certain specialised cases you can do better than O(log(N)). But unless you are dealing with truly gigantic array sizes and satisfy these special cases then your binary search is really the fastest approach.

Answer 3

You could use Arrays.binarySearch to quickly locate 9.0 and 10.0, indeed.

Answer 4

For small numbers of bins a sorted linked list will be most elegant. You scan over it and when you find a number bigger you have the range.

For very large numbers it is worth putting them in a BTree or similar Tree structure in order to get O(log(N)) performance.

In Java you can use a TreeSet for this.

lowerBound = boundaries.headSet(yourNumber).last(); upperBound = boundaries.tailSet(yourNumber).first();

or similar will be O(logN) for large numbers.

Answer 5

If the input numbers are in an array then binary search will be handy. Every time the search fails, indicating the number is not present in the array, the array elements at index low and high will give you the range.

Answer 6

The most efficient (space and time-wise) is to implement this as a modified binary search.

A simple (but less efficient) solution is to replace the array with a NavigableMap<Double, Double> and use floorKey and ceilingKey to find the bounding values. Assuming that you use a TreeMap, this has the same complexity as binary search.

Answer 7

Here's a binary search algorithm I just wrote for you that does the trick:

import java.util.Random;

public class RangeFinder {

    private void find(double query, double[] data) {

        if (data == null || data.length == 0) {
            throw new IllegalArgumentException("No data");
        }

        System.out.print("query " + query + ", data " + data.length + " : ");

        Result result = new Result();
        int max = data.length;
        int min = 0;
        while (result.lo == null && result.hi == null) {

            int pos = (max - min) / 2 + min;
            if (pos == 0 && query < data[pos]) {
                result.hi = pos;
            } else if (pos == (data.length - 1) && query >= data[pos]) {
                result.lo = pos;
            } else if (data[pos] <= query && query < data[pos + 1]) {
                result.lo = pos;
                result.hi = pos + 1;
            } else if (data[pos] > query) {
                max = pos;
            } else {
                min = pos;
            }
            result.iterations++;
        }
        result.print(data);
    }

    private class Result {

        Integer lo;
        Integer hi;
        int iterations;
        long start = System.nanoTime();

        void print(double[] data) {
            System.out.println(

            (lo == null ? "" : data[lo] + " <= ") +

            "query" +

            (hi == null ? "" : " < " + data[hi]) +

            " (" + iterations + " iterations in " +

            ((System.nanoTime() - start) / 1000000.0) + " ms. )");
        }
    }

    public static void main(String[] args) {

        RangeFinder rangeFinder = new RangeFinder();

        // test validation
        try {
            rangeFinder.find(12.4, new double[] {});
            throw new RuntimeException("Validation failed");
        } catch (IllegalArgumentException e) {
            System.out.println("Validation succeeded");
        }
        try {
            rangeFinder.find(12.4, null);
            throw new RuntimeException("Validation failed");
        } catch (IllegalArgumentException e) {
            System.out.println("Validation succeeded");
        }

        // test edge cases with small data set
        double[] smallDataSet = new double[] { 2.0, 7.8, 9.0, 10.5, 12.3 };
        rangeFinder.find(0, smallDataSet);
        rangeFinder.find(2.0, smallDataSet);
        rangeFinder.find(7.9, smallDataSet);
        rangeFinder.find(10.5, smallDataSet);
        rangeFinder.find(12.3, smallDataSet);
        rangeFinder.find(10000, smallDataSet);

        // test performance with large data set
        System.out.print("Preparing large data set...");
        Random r = new Random();
        double[] largeDataSet = new double[20000000];
        largeDataSet[0] = r.nextDouble();
        for (int n = 1; n < largeDataSet.length; n++) {
            largeDataSet[n] = largeDataSet[n - 1] + r.nextDouble();
        }
        System.out.println("done");
        rangeFinder.find(0, largeDataSet);
        rangeFinder.find(5000000.42, largeDataSet);
        rangeFinder.find(20000000, largeDataSet);
    }
}