Найти диапазон числа из массива

Question

Я просто перефразирую вопрос , который я задал недавно.У меня есть отсортированный массив {2.0,7.8,9.0,10.5,12.3}

Если я дал ввод 9,5. Какой самый быстрый способ найти 9,0 и 10,5, чтобы указать, что 9,5 находится между 9,0 и 10,5 (9,5> = 9,0 и <10,5)?Является ли бинарный поиск вариантом? Но поскольку входные данные не обязательно должны быть в массиве. Я не уверен, как мне это сделать. </p>

Также Если есть какая-либо другая подходящая структура данных, пожалуйста, прокомментируйте.

Answer 1

Вы можете использовать Arrays.binarySearch, чтобы быстро найти 9,0 и 10,0, действительно.

Answer 2

Бинарный поиск, безусловно, будет «стандартным» подходом - http://en.wikipedia.org/wiki/Binary_search_algorithm. Скорость равна O (log (N)), а не линейной.

В некоторых специализированных случаях вы можете добиться большего успеха, чем O (log (N)). Но если вы не имеете дело с поистине гигантскими размерами массивов и , удовлетворяющими этим особым случаям, тогда ваш бинарный поиск - действительно самый быстрый подход.

Answer 3

Вот алгоритм двоичного поиска, который я только что написал для вас:

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

Answer 4

Наиболее эффективным (с точки зрения пространства и времени) является его реализация в виде модифицированного двоичного поиска.

Простое (но менее эффективное) решение - заменить массив на NavigableMap<Double, Double> и используйте floorKey и ceilingKey, чтобы найти ограничивающие значения.Предполагая, что вы используете TreeMap, это имеет ту же сложность, что и бинарный поиск.

Answer 5

Если входные числа находятся в массиве, тогда будет полезен двоичный поиск.Каждый раз, когда поиск завершается неудачно, указывая на то, что число отсутствует в массиве, элементы массива с индексами low и high предоставят вам диапазон.

Answer 6

Я бы сделал это так

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 7

Для небольшого количества ячеек отсортированный связанный список будет наиболее элегантным. Вы просматриваете его, и когда вы видите число больше, у вас есть диапазон.

Для очень больших чисел стоит поместить их в BTree или аналогичную древовидную структуру для получения производительности O (log (N)).

В Java вы можете использовать TreeSet для этого.

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

или подобное будет O (logN) для больших чисел.