2014-02-10 92 views
-3

如何通過二進制搜索索引位置

int curIndex = Collections.binarysearch(myList,"String"); 
int highIndex = ? 
+0

你這是什麼意思lowIndex?它返回列表中項目的索引(如果它存在)。 – Reddy

+0

你是否在第一次和最後一次出現「String」的索引之後(假設有多個出現),或者你是否像'highIndex = lowIndex +「String」.length()'之類的東西? – Edd

回答

4

你已經做出不正確的假設鍵值獲得Collections.binarysearch()最高和最低指數的位置是:返回的值將以最低的指數。從documentation

如果列表包含多個元素等於指定的對象,則不能保證會找到哪個元素。

基本上,一旦你發現一個比賽,你只需要走的列表,直到找到不匹配,以獲得最低的指數,然後步行列表,直到找到一個非匹配得到最高的索引。

int found = Collections.binarySearch(myList, "String"); 
int lowIndex = found; 
while (lowIndex > 0 && myList.get(lowIndex - 1).equals("String")) { 
    lowIndex--; 
} 
int highIndex = found; 
while (highIndex + 1 < myList.size() 
     && myList.get(highIndex + 1).equals("String")) { 
    highIndex++; 
} 

(你可以重寫這些while循環爲for循環用空的身體,如果你想,但我覺得這更易讀。)