Java等价于c ++ equal_range（或lower_bound＆upper_bound）

我有一个对象列表排序，我想找到一个对象的第一次出现和最后一次出现。 在C ++中，我可以轻松地使用std :: equal_range（或者只使用一个lower_bound和一个upper_bound）。

例如：

bool mygreater (int i,int j) { return (i>j); } int main () { int myints[] = {10,20,30,30,20,10,10,20}; std::vector v(myints,myints+8); // 10 20 30 30 20 10 10 20 std::pair<std::vector::iterator,std::vector::iterator> bounds; // using default comparison: std::sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30 bounds=std::equal_range (v.begin(), v.end(), 20); // ^ ^ // using "mygreater" as comp: std::sort (v.begin(), v.end(), mygreater); // 30 30 20 20 20 10 10 10 bounds=std::equal_range (v.begin(), v.end(), 20, mygreater); // ^ ^ std::cout << "bounds at positions " << (bounds.first - v.begin()); std::cout << " and " << (bounds.second - v.begin()) << '\n'; return 0; } 

在Java中，似乎没有简单的等价？ 我该如何处理相同的范围

 List myList; 

顺便说一句，我使用的是标准导入java.util.List;

Answer 1

在Java中，使用Collections.binarySearch在排序列表中查找相等范围的下限（ Arrays.binarySearch为数组提供类似的function）。 然后继续线性迭代，直到达到相等范围的末尾。

这些方法适用于实现Comparable接口的方法。 对于未实现Comparable ，您可以提供自定义 Comparator的实例，以Comparator特定类型的元素。

Answer 2

你可以尝试这样的事情：

  public class TestSOF { private ArrayList  testList = new ArrayList (); private Integer first, last; public void fillArray(){ testList.add(10); testList.add(20); testList.add(30); testList.add(30); testList.add(20); testList.add(10); testList.add(10); testList.add(20); } public ArrayList getArray(){ return this.testList; } public void sortArray(){ Collections.sort(testList); } public void checkPosition(int element){ if (testList.contains(element)){ first = testList.indexOf(element); last = testList.lastIndexOf(element); System.out.println("The element " + element + "has it's first appeareance on position " + first + "and it's last on position " + last); } else{ System.out.println("Your element " + element + " is not into the arraylist!"); } } public static void main (String [] args){ TestSOF testSOF = new TestSOF(); testSOF.fillArray(); testSOF.sortArray(); testSOF.checkPosition(20); } 

}

Answer 3

在二进制搜索中，当您找到元素时，您可以继续在其左侧进行二进制搜索，以便找到第一个匹配项并向右查找以查找最后一个元素。 这个想法应该用代码清楚：

 /* B: element to find first or last occurrence of searchFirst: true to find first occurrence, false to find last */ Integer bound(final List A,int B,boolean searchFirst){ int n = A.size(); int low = 0; int high = n-1; int res = -1; //if element not found int mid ; while(low<=high){ mid = low+(high-low)/2; if(A.get(mid)==B){ res=mid; if(searchFirst){high=mid-1;} //to find first , go left else{low=mid+1;} // to find last, go right } else if(B>A.get(mid)){low=mid+1;} else{high=mid-1;} } return res; } 

Answer 4

 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Collections; import java.util.Vector; public class Bounds { public static void main(String[] args) throws IOException { Vector data = new Vector<>(); for (int i = 29; i >= 0; i -= 2) { data.add(Float.valueOf(i)); } Collections.sort(data); float element = 14; BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out)); String string = bf.readLine(); while (!string.equals("q")) { element=Float.parseFloat(string); int first = 0; int last = data.size(); int mid; while (first < last) { mid = first + ((last - first) >> 1); if (data.get(mid) < element) //lower bound. for upper use <= first = mid + 1; else last = mid; } log.write("data is: "+data+"\n"); if(first==data.size()) first=data.size()-1; log.write("element is : " + first+ "\n"); log.flush(); string= bf.readLine(); } bf.close(); } } 

这是与c ++类似的lower_bound和upper_bound的实现。 请注意，您要搜索的元素不需要出现在向量或列表中。 此实现仅提供元素的上限和下限。