Java 等价于 c++ equal_range（或lower_bound & upper_bound）
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15603832/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java equivalent of c++ equal_range (or lower_bound & upper_bound)
提问by Gob00st
I have a List of object sorted and I want to find the first occurrence and the last occurrence of an object. In C++, I can easily use std::equal_range (or just one lower_bound and one upper_bound).
我有一个已排序的对象列表，我想找到对象的第一次出现和最后一次出现。在 C++ 中，我可以轻松使用 std::equal_range（或仅使用一个 lower_bound 和一个 upper_bound）。
For example:
例如：
bool mygreater (int i,int j) { return (i>j); }
int main () {
int myints[] = {10,20,30,30,20,10,10,20};
std::vector<int> v(myints,myints+8); // 10 20 30 30 20 10 10 20
std::pair<std::vector<int>::iterator,std::vector<int>::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;
}
In Java, there seems to be no simple equivalence? How should I do with the equal range with
在Java中，似乎没有简单的等价物？我应该如何处理相同的范围
List<MyClass> myList;
By the way, I am using a standard import java.util.List;
顺便说一下，我使用的是标准导入 java.util.List;
采纳答案by dasblinkenlight
In Java, you use Collections.binarySearchto find the lower bound of the equal range in a sorted list (Arrays.binarySearchprovides a similar capability for arrays). Then you continue iterating linearly until you hit to the end of the equal range.
在 Java 中，您用于Collections.binarySearch在排序列表中查找相等范围的下限（Arrays.binarySearch为数组提供类似的功能）。然后继续线性迭代，直到到达相等范围的末尾。
These methods work for methods implementing the Comparableinterface. For classes that do not implement the Comparable, you can supply an instance of a customComparatorfor comparing the elements of your specific type.
这些方法适用于实现Comparable接口的方法。对于未实现 的类Comparable，您可以提供一个自定义实例Comparator来比较您的特定类型的元素。
回答by Andrushenko Alexander
Java have already built-in binary search functionality that calculates lower/upper bounds for an element in an array, there is no need to implement custom methods.
Java 已经内置了二进制搜索功能，可以计算数组中元素的下限/上限，无需实现自定义方法。
When we speak about upper/lower bounds or equal ranges, we always mean indexes of a container (in this case of ArrayList), and not the elements contained. Let's consider an array (we assume the array is sorted, otherwise we sort it first):
当我们谈论上限/下限或相等范围时，我们总是指容器的索引（在这种情况下是 ArrayList），而不是包含的元素。让我们考虑一个数组（我们假设数组已排序，否则我们先对其进行排序）：
List<Integer> nums = new ArrayList<>(Arrays.asList(2,3,5,5,7,9,10,18,22));
The "lower bound" function must return the index of the array, where the element must be inserted to keep the array sorted. The "upper bound" must return the index of the smallest element in the array, that is bigger thanthe looked for element. For example
“下限”函数必须返回数组的索引，必须插入元素以保持数组排序。“上限”必须返回数组中最小元素的索引，该索引大于查找的元素。例如
lowerBound(nums, 6)
must return 3, because 3 is the position of the array (starting counting with 0), where 6 must be inserted to keep array sorted.
必须返回 3，因为 3 是数组的位置（从 0 开始计数），其中必须插入 6 以保持数组排序。
The
这
upperBound(nums, 6)
must return 4, because 4 is the position of the smallestelement in the array, that is biggerthan 5 or 6, (number 7 on position 4).
必须返回4，因为4是的位置最小数组中元素，即更大的比5或6中，（在第4位号7）。
In C++ in standard library the both algorithms already implemented in standard library. In Java you can use
在标准库中的 C++ 中，这两种算法都已经在标准库中实现了。在 Java 中，您可以使用
Collections.binarySearch(nums, element)
to calculate the position in logarithmic time complexity.
以对数时间复杂度计算位置。
If the array contains the element, Collections.binarySearchreturns the first index of the element (in the array above 2). Otherwise it returns a negative number that specifies the position in the array of the next bigger element, counting backwards from the last index of the array. The number found in this position is the smallest element of the array that is bigger than the elementyou look for.
如果数组包含该元素，则Collections.binarySearch返回该元素的第一个索引（在 2 以上的数组中）。否则，它返回一个负数，指定下一个较大元素在数组中的位置，从数组的最后一个索引开始向后计数。在此位置找到的数字是数组中比您要查找的元素大的最小元素。
For example, if you call
例如，如果您调用
int idx = Collections.binarySearch(nums, 6)
the function returns -5. If you count backwards from the last index of the array (-1, -2, ...) the index -5 points to number 7 - the smallest number in the array that is bigger than the element 6.
该函数返回-5。如果从数组的最后一个索引 (-1, -2, ...) 向后计数，则索引 -5 指向数字 7 - 数组中大于元素 6 的最小数字。
Conclusion: if the sorted array containsthe looked for element, the lower bound is the position of the element, and the upper bound is the position of the next bigger element.
结论：如果排序后的数组包含要查找的元素，则下界为该元素的位置，上界为下一个较大元素的位置。
If the array does not containsthe element, the lower bound is the position
如果数组不包含该元素，则下限为位置
Math.abs(idx) - 2
and the upper bound is the position
上限是位置
Math.abs(idx) - 1
where
在哪里
idx = Collections.binarySearch(nums, element)
And please always keep in mind the border cases. For example, if you look for 1 in the above specified array:
并且请始终牢记边界情况。例如，如果您在上面指定的数组中查找 1：
idx = Collections.binarySearch(nums, 1)
The functon returns -1. So, the upperBound = Math.abs(idx) - 1 = 0 - the element 2 at position 0. But there is no lower bound for element 1, because 2 is the smallest number in the array. The same logic applies to elements bigger than the biggest number in the array: if you look for lower/upper bounds of number 25, you will get
该函数返回-1。因此， upperBound = Math.abs(idx) - 1 = 0 - 位置 0 处的元素 2。但元素 1 没有下限，因为 2 是数组中的最小数字。相同的逻辑适用于大于数组中最大数字的元素：如果您查找数字 25 的下限/上限，您将得到
idx = Collections.binarySearch(nums, 25)
ix = -10. You can calculate the lower bound : lb = Math.abs(-10) - 2 = 8, that is the last index of the array, but there is no upper bound, because 22 is already biggest element in the array and there is no element at position 9.
ix = -10。可以计算下界：lb = Math.abs(-10) - 2 = 8，即数组的最后一个索引，但没有上界，因为22已经是数组中最大的元素，没有位置 9 处的元素。
The equal_range specifies all indexes of the array in the range starting from the lower bound index up to (but not including) the upper bound. For example, the equal range of number 5 in the array above are indexes
equal_range 指定从下限索引到（但不包括）上限的范围内数组的所有索引。例如上面数组中数字5的相等范围是索引
[2,3]
Equal range of number 6 is empty, because there is no number 6 in the array.
数字 6 的相等范围为空，因为数组中没有数字 6。
回答by Survivor
You can try something like this:
你可以尝试这样的事情：
public class TestSOF {
private ArrayList <Integer> testList = new ArrayList <Integer>();
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);
}
}
}
回答by RJN_WLY
In binary search , when you find the element then you can keep doing binary search to its left in order to find first occurrence and to right in order to find last element. The idea should be clear with the code:
在二分搜索中，当您找到元素时，您可以继续向其左侧进行二分搜索以找到第一次出现，向右进行二分搜索以找到最后一个元素。这个想法应该用代码清楚：
/*
B: element to find first or last occurrence of
searchFirst: true to find first occurrence, false to find last
*/
Integer bound(final List<Integer> 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;
}
回答by HariUserX
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<Float> 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();
}
}
This is the implementation for lower_bound and upper_bound similar to c++. Note that the element you are searching for need not be present in the vector or list. This implementation only gives the element's upper and lower bounds.
这是lower_bound 和upper_bound 的实现，类似于c++。请注意，您要搜索的元素不必出现在向量或列表中。此实现仅给出元素的上限和下限。
