Collections.binarySearch() in Java with Examples
Last Updated :
30 Mar, 2023
java.util.Collections.binarySearch() method is a java.util.Collections class method that returns position of an object in a sorted list.
// Returns index of key in sorted list sorted in
// ascending order
public static int binarySearch(List slist, T key)
// Returns index of key in sorted list sorted in
// order defined by Comparator c.
public static int binarySearch(List slist, T key, Comparator c)
If key is not present, the it returns "(-(insertion point) - 1)".
The insertion point is defined as the point at which the key
would be inserted into the list.
The method throws ClassCastException if elements of list are not comparable using the specified comparator, or the search key is not comparable with the elements.
Searching an int key in a list sorted in ascending order:
Java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class GFG {
public static void main(String[] args)
{
List<Integer> al = new ArrayList<Integer>();
al.add(1);
al.add(2);
al.add(3);
al.add(10);
al.add(20);
int index = Collections.binarySearch(al, 10);
System.out.println(index);
index = Collections.binarySearch(al, 13);
System.out.println(index);
}
}
|
Searching an int key in a list sorted in descending order.
Java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class GFG {
public static void main(String[] args)
{
List<Integer> al = new ArrayList<Integer>();
al.add(100);
al.add(50);
al.add(30);
al.add(10);
al.add(2);
int index = Collections.binarySearch(
al, 50, Collections.reverseOrder());
System.out.println("Found at index " + index);
}
}
|
Searching in a list of user-defined class objects:
Java
import java.util.*;
class Binarysearch {
public static void main(String[] args)
{
List<Domain> l = new ArrayList<Domain>();
l.add(new Domain(10, "www.geeksforgeeks.org"));
l.add(new Domain(20, "practice.geeksforgeeks.org"));
l.add(new Domain(30, "code.geeksforgeeks.org"));
l.add(new Domain(40, "www.geeksforgeeks.org"));
Comparator<Domain> c = new Comparator<Domain>() {
public int compare(Domain u1, Domain u2)
{
return u1.getId().compareTo(u2.getId());
}
};
int index = Collections.binarySearch(
l, new Domain(10, null), c);
System.out.println("Found at index " + index);
index = Collections.binarySearch(
l, new Domain(5, null), c);
System.out.println(index);
}
}
class Domain {
private int id;
private String url;
public Domain(int id, String url)
{
this.id = id;
this.url = url;
}
public Integer getId() { return Integer.valueOf(id); }
}
|
Output
Found at index 0
-1
Complexity Analysis:
Time Complexity:
The time complexity of the binarySearch() method in the Collections class is O(log n), where n is the size of the list.
Auxiliary Space:
The space complexity of the binarySearch() method in the Collections class is O(1), as it does not require any additional data structures to be created.
Arrays.binarysearch() vs Collections.binarySearch()
Arrays.binarysearch() works for arrays which can be of primitive data type also. Collections.binarysearch() works for objects Collections like ArrayList and LinkedList.
Important Points:
- If input list is not sorted, the results are undefined.
- If there are duplicates, there is no guarantee which one will be found.
- This method runs in log(n) time for a “random access” list like ArrayList. If the specified list does not implement the RandomAccess interface and is large, this method will do an iterator-based binary search that performs O(n) link traversals and O(log n) element comparisons.
Reference :
https://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#binarySearch(java.util.List,%20T)
Please Login to comment...