Alternative implementation of lower_bound() and upper_bound() in Java
The following is the purpose of lower_bound() function:
The std::lower_bound() method in C++ is used to return an iterator pointing to the first element in the given range which has a value greater than or equal to the given value.
There is another method std::upper_bound() which return an iterator pointing to the first element in the given range which is greater than the given value.
Note: The list should be already sorted before calling these functions.
There is no predefined function for lower_bound in java for List containers. Although there are inbuilt functions such as Arrays.BinarySearch() and Containers.BinarySearch() but they just return the index if element is present in the list otherwise -1 and that too is not very consistent.
There are two alternatives to this in Java.
- Using self defined lower_bound
- Using TreeMap class.
Both of these will be discussed with examples.
Using self defined lower_bound:
It is not very difficult to alter the traditional binary search method to change it according to our need. The following is the code snippet for implementation of lower_bound in java:
public static int lower_bound(ArrayList<Integer> ar,int k)
{
int s=0;
int e=ar.size();
while (s !=e)
{
int mid = s+e>>1;
if (ar.get(mid) <k)
{
s=mid+1;
}
else
{
e=mid;
}
}
if(s==ar.size())
{
return -1;
}
return s;
}Implementation of upper_bound is exactly the same except for the if condition we write ar.get(mid)≤k instead of ar.get(mid)<k.
public static int upper_bound(ArrayList<Integer> ar,int k)
{
int s=0;
int e=ar.size();
while (s !=e)
{
int mid = s+e>>1;
if (ar.get(mid) <=k)
{
s=mid+1;
}
else
{
e=mid;
}
}
if(s==ar.size())
{
return -1;
}
return s;
}Sample Example:
Check this problem. Although you can only solve this in c++ in Hackerrank platform but the implementation in Java will be a good practice.
C++ Code:
#include <vector>#include <iostream>#include <algorithm>using namespace std;int main(){vector<int> ar;int n;cin>>n;for(int x=0;x<n;x++){int d;cin>>d;ar.push_back(d);}int q;cin>>q;while(q--){int d;cin>>d;auto it=lower_bound(ar.begin(),ar.end(),d);if(*it==d){cout<<"Yes ";}else{cout<<"No ";}cout<<it-ar.begin()+1<<"\n";}return 0;}
Java Code:
import java.util.ArrayList;
import java.util.Scanner;
class Solution
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
ArrayList<Integer> ar=new ArrayList<>();
for(int x=0;x<n;x++)
{
ar.add(sc.nextInt());
}
int q=sc.nextInt();
while(q-->0)
{
int d=sc.nextInt();
int i=lower_bound(ar,d);
if(ar.get(i)==d)
{
System.out.print("Yes ");
}
else
{
System.out.print("No ");
}
System.out.println(i+1);
}
}
public static int lower_bound(ArrayList<Integer> ar,int k)
{
int s=0;
int e=ar.size();
while (s !=e)
{
int mid = s+e>>1;
if (ar.get(mid) <k)
{
s=mid+1;
}
else
{
e=mid;
}
}
if(s==ar.size())
{
return -1;
}
return s;
}
}This is the basic implementation of lower_bound in java.
Using TreeMap Class
Sometimes we have to remove an element after selecting it from the List. But the time complexity of remove operation in List Containers is O(n) in average and worst case. Which may lead to TLE at times. To overcome we may use the TreeMap data structure in java. Like HashMap, TreeMap also provides us insertion, deletion and searching time complexity of O(1) but unlike the former, TreeMap also keeps the value in sorted order (it uses Red Black Tree to store data).
The only drawback of using TreeMap is that it does not keep duplicate values. In order to do that we have to create our own Datatype and add a compare function to it as well.
Basic Syntax of TreeMap is as follows:
TreeMap<K,K> map=new TreeMap<>();
...
...
...K i=map.lowerKey(d);
This problem is a perfect example where we cannot use our lower_bound because of extra time required for delete operation and we have to create our own data type to store multiple duplicate values.
C++ Solution:
#include<vector>
#include<iostream>
#include<set>
#include<algorithm>
#include<array>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
set<array<int,2>> s;
for(int x=0;x<n;x++)
{
int a;
cin>>a;
s.insert({a,x});
}
for(int x=0;x<m;x++)
{
int t;
cin>>t;
auto it=s.lower_bound({t+1,0});
if(it==s.begin())
{
cout<<"-1\n";
}
else
{
--it;
cout<<(*it)[0]<<"\n";
s.erase(it);
}
}
return 0;
}Java Solution:
import java.io.*;
import java.util.*;
public class SS4
{
static PrintWriter out = new PrintWriter((System.out));
public static void main(String args[]) throws IOException
{
Reader sc = new Reader();
int n = sc.nextInt();
int m = sc.nextInt();
TreeMap<Data,Integer> ar=new TreeMap<>(new Sort());
for(int x=0;x<n;x++)
{
ar.put(new Data(sc.nextInt(),x),0);
}
for(int y=0;y<m;y++)
{
int b = sc.nextInt();
Data i = ar.lowerKey(new Data(b+1, 0));
if(i!=null)
{
out.println(i.i);
ar.remove(i);
}
else
{
out.println(-1);
}
}
out.close();
}
static class Reader
{
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Reader()
{
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public Reader(String file_name) throws IOException
{
din = new DataInputStream(new FileInputStream(file_name));
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public String readLine() throws IOException
{
byte[] buf = new byte[64]; // line length
int cnt = 0, c;
while ((c = read()) != -1)
{
if (c == '\n')
break;
buf[cnt++] = (byte) c;
}
return new String(buf, 0, cnt);
}
public int nextInt() throws IOException
{
int ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do
{
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public long nextLong() throws IOException
{
long ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
}
while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public double nextDouble() throws IOException
{
double ret = 0, div = 1;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
}
while ((c = read()) >= '0' && c <= '9');
if (c == '.')
{
while ((c = read()) >= '0' && c <= '9')
{
ret += (c - '0') / (div *= 10);
}
}
if (neg)
return -ret;
return ret;
}
private void fillBuffer() throws IOException
{
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}
private byte read() throws IOException
{
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}
public void close() throws IOException
{
if (din == null)
return;
din.close();
}
}
}
class Data
{
int i, j;
public Data(int i,int j)
{
this.i=i;
this.j=j;
}
}
class Sort implements Comparator<Data>
{
@Override
public int compare(Data a, Data b)
{
if(a.i!=b.i)
{
return a.i - b.i;
}
else
{
return a.j-b.j;
}
}
}Bonus: What if we need a function which returns the value less than or equal to the given value? We will just have to return index of lower_bound()-1 as index. Given below is the implementation of the same.
public static int get_floor(ArrayList<Integer> ar,int k)
{
int s=0,e=ar.size();
while (s != e)
{
int mid = s + e >> 1;
if (ar.get(mid) <= k)
{
s = mid + 1;
}
else
{
e = mid;
}
}
return s-1;
}Thanks for reading my article. Please comment if you have any query.
