檢查一個int是否在一個數組中的兩個項目之間

好吧，所以我正在使用java中的一個調平系統。我有這個從我剛纔的問題來定義級別「EXP」的要求：檢查一個int是否在一個數組中的兩個項目之間

int[] levels = new int[100]; 
    for (int i = 1; i < 100; i++) { 
     levels[i] = (int) (levels[i-1] * 1.1); 
    }

現在，我的問題是如何將確定一個EXP水平是兩個不同的整數之間的數組中，然後返回低兩個？我發現有東西關閉，但不是我正在尋找here它說二進制搜索。一旦我找到exp之間的哪個值，我就可以確定用戶的級別。或者，如果其他人有更好的主意，請不要猶豫，提及它。請原諒我可能的nooby錯誤，我是Java新手。預先感謝任何答案。

解決，感謝所有美好的答案。

來源

2014-02-26 EhhChris

「我發現一些接近，但不完全是我正在尋找」爲什麼這個不太你在找什麼？看起來你確實需要什麼。 –

什麼讓你不單獨存儲級別？ – Cubic

@ peter.petrov - 定位數組中一個固定點的索引（位置'i'，使得'array [i] == i'）。這完全不是OP所需要的，我不知道OP爲什麼說它「接近」。 –

對於一般排序的數組數組，二分搜索是要走的路，即O（log n）。但是因爲數字之間存在數學關係（每個數字是前一個數字的1.1倍），請利用這一事實。您正在尋找的最大指數level這樣

levels[0] * Math.pow(1.1, level) <= exp

求解水平，

level = log{base 1.1}(exp/levels[0])

考慮到該日誌_一個（B）= LN（B）/ LN的事實優勢（ a）...

int level = (int) Math.log(exp/levels[0])/Math.log(1.1);

由於數學關係，你只需要這個計算，而不需要搜索，所以它是O（1）。

double base = 1; 
double factor = 1.1; 

for (double score : Arrays.asList(1.0, 1.1, 1.3, 8.6, 9.46)) 
{ 
    int level = (int) (Math.log(score/base)/Math.log(factor)); 
    System.out.println(level); 
}

打印

來源

2014-02-26 22:58:17 rgettman

是的，你應該在這裏進行二分搜索，因爲你的數組元素似乎被排序。
這從您初始化他們的方式。
你當然也可以做線性搜索，但前者更好。

來源

2014-02-26 22:42:51

謝謝！你能簡單地解釋二進制搜索，並可能給我一個容易理解的例子嗎？我會以任何方式做一些研究，但越多越好。 – EhhChris

@EhhChris解釋二進制搜索將超出這個問題的範圍;二進制搜索是現有最常用的算法之一，您幾乎可以在任何地方找到幾乎任何語言的參考實現。 – Cubic

如果您的電話簿按名稱排序，並且您正在尋找Nicholas，請打開該書的中間頁面。說你在那裏看到了邁克爾的名字。所以現在，在本書的第一部分搜索邁克爾<尼古拉斯是沒有意義的。那麼你只能在本書的第二部分以完全相同的方式進行搜索。這是二進制搜索。二進制搜索在每個步驟中將搜索空間削減一半。 –

可以使用built-in binary search method：

int exp = . . . 
int pos = Arrays.binarySearch(levels, exp); 
if (pos < 0) { 
    // no exact match -- change pos to the insertion index 
    pos = -pos - 1; 
    // Now exp is between levels[pos] and levels[pos - 1] 
    // (or less than levels[0] if pos is now 0) 
} else { 
    // exp is exactly equal to levels[pos] 
}

來源

2014-02-26 22:45:45

爲什麼不直接使用Arrays Class？

int valueToFind = 100; 
int index = Arrays.binarySearch(levels, valueToFind)

來源

2014-02-26 22:46:53 jeremyjjbrown

檢查一個int是否在一個數組中的兩個項目之間

回答

相關問題