找出一個值「適合」在一個數組中的位置？

我有什麼應該是一個非常簡單的算法一個麻煩，但由於某種原因，我的頭不能正常工作找出一個值「適合」在一個數組中的位置？

我有數值的Array（工作量太大？）：10，20， 30，40，100，1000，5000，100000]我想檢查哪一個是數組中的下一個「項目」。

例如，

給出的數字10

，我的算法應該返回10中給出
數字1，我的算法應該返回10中給出的編號50
，我的算法應該返回100 。
提供的電話號碼99999999，我的算法應該返回100000

在僞代碼，我在想：

for previousValue, nextValue in values: 
    if (previousValue < value && nextValue >= value): 
    return nextValue 
return values[max]

如果任何人都可以指出我疲憊的大腦，我錯過了它會很好。謝謝！

來源

2013-10-08 dornad

你的數組是否總是排序？ –

即使沒有排序，我們也可以事先進行排序並使用二進制搜索。 – favoretti

請檢查我的答案。 –

假設數組已經排序，您的解決方案正常工作。但是，爲了更清楚我會如下改寫：

prev = 0 
    for(v in values){ 
     if(target > prev && target <= v) 
       return v 
     prev = v 
    } 
    return values[values.length-1]

來源

2013-10-09 05:39:43 Niki

在紅寶石：

find 0,values.length,val 
def find left,right,val 
    if left == right || left > right then return values[left] 
    if val > values[(right + left)/2] 
     find (right + left)/2, right, val 
    else 
     find left, (right + left)/2, val 
    end 
end

來源

2013-10-09 05:53:49

陣列不必進行分類。對數組進行排序具有O（nlogn）時間複雜度。您可以在theta（n）時間檢查數組中的每個元素。

假設陣列是arr和比較產品item並且陣列arr包含至少一個元素大於或等於item：

在java中

public static int find_greater(int[] arr,int item) 
{ 
    int j=0; 
    int previous =0; 
    for(int i=0;i<arr.length;i++){ 
     if(arr[i]>=item){ 
      if(j==0){ 
       previous = arr[i]; 

      }else{ 
       if(arr[i]<previous) 
       { 
        previous = arr[i]; 
       } 
      } 
      j++; 

     } 
    } 
    return previous; 
}

這裏，我去通過陣列並保留變量previous，這是最大的數字大於或等於item。此過程的運行時間爲theta(N)，其中N爲arr.length。

來源

2013-10-09 06:16:27

我可能將這個數組表示爲一棵樹。要找出最接近的最大值，我只需在樹中查找，就像我會找到一把鑰匙一樣，並始終跟蹤最接近的值。當我到達節點的末尾時，我返回最接近的值。

與其他答案相比，這是另一種選擇。你可以在這個線程中檢查How to find the closest element to a given key value in a binary search tree?

來源

2013-10-09 08:23:28

找出一個值「適合」在一個數組中的位置？

回答

相關問題