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

Question

Я просто перефразирую 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)? Является ли двоичный поиск опцией? Но так как вход не обязательно должен быть в массиве. Я не уверен, как это сделать.

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

Answer 1

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

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 2

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

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 3

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

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

Answer 4

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

Answer 5

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

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

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

lowerBound = границы.headSet (yourNumber) .last(); upperBound = limits.tailSet (yourNumber) .first();

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

Answer 6

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

Answer 7

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

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