Javaライブラリ関数を使用するだけでなく、独自のLowerBound関数とUpperBound関数を定義することによって、下限と上限を見つけることができます。
{＃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 =配列内のその数値よりちょうど大きい次の数値のインデックス。ieub =その数値のインデックス+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を超える場合、番号は複数回発生します。この場合
、 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;
}