查找數組的一個數字的範圍

我只是改寫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