查找数组的一个数字的范围

我只是改写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 <）之间的最快方法是什么？二进制搜索是一个选项吗？但是因为输入不需要在数组中。我不知道我应该怎么做。

另外如果有其他任何适合的数据结构请评论。

2010-08-19 Emil

接受的回答你刚才的问题，请。 – 2010-08-19 09:16:04

这里是一个二进制搜索算法我只写了你做的伎俩：

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

来源

2010-08-19 14:35:26

我会那样做

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

来源

2010-08-19 09:21:50 Markus

这就是线性扫描。对于小型阵列来说不错，但Emil想要一个更优雅的解决方案（我假设Emil知道如何以某种方式实现它）。 – helios 2010-08-19 09:28:21

二进制搜索肯定会是“标准”的做法 - http://en.wikipedia.org/wiki/Binary_search_algorithm。速度是O（log（N））而不是线性。

在某些特殊情况下，您可以比O（log（N））做得更好。但除非你正在处理真正庞大的阵列尺寸和满足这些特殊情况，那么你的二分查找确实是最快的方法。

来源

2010-08-19 09:22:01

实际上，您可以使用Arrays.binarySearch快速找到9.0和10.0。

来源

2010-08-19 09:24:40 Riduidel