Java 相当于 c++ equal_range（或 lower_bound & upper_bound）Lower_Bound和Upper_Bound的执行情况

binary-search java lower-bound upperbound

2022-09-02 03:55:04

我有一个对象列表排序，我想找到一个对象的第一次出现和最后一次出现。在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<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;
}

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

List<MyClass> myList;

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

答案 1

在 Java 中，您可以使用 Collections.binarySearch 在排序列表中查找相等范围的下限（为数组提供类似的功能）。这为您提供了相等范围内的位置，没有进一步的保证：Arrays.binarySearch

如果列表包含等于指定对象的多个元素，则无法保证找到哪一个元素。

然后，您向前和向后线性迭代，直到达到相等范围的末尾。

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

答案 2

我们可以在java库函数的帮助下找到下限和上限，也可以通过定义我们自己的下界和上限函数来找到下限和上限。

{#case-1}

如果数字不存在，则下限和上限将相同.即在这种情况下，lb和ub将是数组的插入点，即应插入数字以保持数组排序的点。

示例 1：

6 1 // 6 is the size of the array and 1 is the key
2 3 4 5 6 7 here lb=0 and ub=0 (0 is the position where 1 should be inserted to keep the array sorted)

6 8 // 6 is the size of the array and 8 is the key
2 3 4 5 6 7  here lb=6 and ub=6 (6 is the position where 8 should be inserted to keep the array sorted)

6 3 // 6 is the size of the array and 3 is the key
1 2 2 2 4 5  here lb=4 and ub=4 (4 is the position where 3 should be inserted to keep the array sorted)

{#case-2（a）}

如果该数字存在且频率为 1。即发生次数为 1

lb=该数字的索引。
ub=下一个数字的索引，该数字仅大于数组中的该数字.即ub=该数字的索引+1

示例 2：

6 5 // 6 is the size of the array and 5 is the key
1 2 3 4 5 6 here lb=4 and ub=5

{#case-2（b）}

如果数字存在并且频率大于 1。数字发生多次 times.in 在这种情况下，lb 将是该数字第一次出现的索引。ub 将是该数字+1 的最后一次出现的索引。即，该数字的索引仅大于数组中的键。

示例 3：

 11 5 // 11 is the size of the array and 5 is the key
 1 2 3 4 5 5 5 5 5 7 7 here lb=4 and ub=9

Lower_Bound和Upper_Bound的执行情况

方法1：按库函数

a 是数组，x 是目标值

int lb=Arrays.binarySearch(a,x); // for lower_bound

int ub=Arrays.binarySearch(a,x); // for upper_bound

if(lb<0) {lb=Math.abs(lb)-1;}//if the number is not present

else{ // if the number is present we are checking 
    //whether the number is present multiple times or not
    int y=a[lb];
    for(int i=lb-1; i>=0; i--){
        if(a[i]==y) --lb;
        else break;
    }
}
  if(ub<0) {ub=Math.abs(ub)-1;}//if the number is not present

  else{// if the number is present we are checking 
    //whether the number is present multiple times or not
    int y=a[ub];
    for(int i=ub+1; i<n; i++){
        if(a[i]==y) ++ub;
        else break;
    }
    ++ub;
}

方法2：通过定义自己的函数

对于下限

static int LowerBound(int a[], int x) { // x is the target value or key
  int l=-1,r=a.length;
  while(l+1<r) {
    int m=(l+r)>>>1;
    if(a[m]>=x) r=m;
    else l=m;
  }
  return r;
}

Upper_Bound

 static int UpperBound(int a[], int x) {// x is the key or target value
    int l=-1,r=a.length;
    while(l+1<r) {
       int m=(l+r)>>>1;
       if(a[m]<=x) l=m;
       else r=m;
    }
    return l+1;
 }

或者我们可以使用

int m=l+(r-l)/2;

但是如果我们使用

int m=(l+r)>>>1; // it is probably faster

但是使用上述任何计算m的公式都会防止溢出

在 C 和 C++ （>>>）运算符不存在的情况下，我们可以这样做：

int m= ((unsigned int)l + (unsigned int)r)) >> 1;

在计划中实施：

import java.util.*;
import java.lang.*;
import java.io.*;
public class Lower_bound_and_Upper_bound {

public static void main (String[] args) throws java.lang.Exception
{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer s = new StringTokenizer(br.readLine());
    int n=Integer.parseInt(s.nextToken()),x=Integer.parseInt(s.nextToken()),a[]=new int[n];
    s = new StringTokenizer(br.readLine());
    for(int i=0; i<n; i++) a[i]=Integer.parseInt(s.nextToken());
    Arrays.sort(a);// Array should be sorted. otherwise lb and ub cant be calculated
    int u=UpperBound(a,x);
    int l=LowerBound(a,x);
    System.out.println(l+" "+u);
 }
}

# 等效C++码，用于计算下限和上限

  #include<bits/stdc++.h>
  #define IRONMAN ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  using namespace std;
  typedef long long int ll;
  int main() {
    IRONMAN
    int n,x;cin>>n>>x;
    vector<int> v(n);
    for(auto &i: v) cin>>i;
    ll lb=(lower_bound(v.begin(),v.end(),x))-v.begin();// for calculating lb
    ll ub=(upper_bound(v.begin(),v.end(),x))-v.begin();// for calculating ub
    cout<<lb<<" "<<ub<<"\n";
    return 0;
  }