Binary Search in C++ Standard Library (STL) and Java Collections

In this post, we will see how to search for a given target value in a sorted array of integers using binary search implementation provided by C++ standard library (STL) and Java collection framework.


 

1. Binary Search implementation in C++ standard library:

C++ STL library has std::binary_search function defined in the header “algorithm”. It takes the iterators to starting and ending positions of a sorted sequence and returns true if the target value is found; otherwise it returns false. This search operation takes O(log(n)) time and is very efficient even for large arrays. We can use it as shown below for an integer array:

 

Download   Run Code

Output:

Element found at index 3

 

2. Binary Search implementation in Java collection framework:

In Java, we can use binarySearch() method provided by the Arrays class. It searches the specified sorted array (or the range of it) for the target value using the binary search algorithm. It is overloaded for all primitive types and can also sort an object array using a comparator.

Unlike C++ std::binary_search which returns true on success, Arrays.binarySearch() returns index of the search key, if it is contained in the array; otherwise a negative value is returned. If the sorted array is not passed to it, the results are undefined. It can be used as shown below for an integer array:

 

Download   Run Code

Output:

Element found at index 3

 

We can also write our own implementation of binary search algorithm as covered here in detail.

 
Thanks for reading.

Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of