Binary Search in C++ STL and Java Collections
This post will discuss how to search for a given target value in a sorted array of integers using binary search implementation provided by the C++ standard library (STL) and Java Collection framework.
1. Binary Search in STL
In C++, STL library has std::binary_search
function defined in the header “algorithm”. It takes the iterators to the starting and ending positions of a sorted sequence and returns true if the target value is found; otherwise, returns false. This search operation takes O(log(n)) time and is very efficient even for large sorted arrays.
The following C++ program demonstrates its usage on a sorted integer array:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include <iostream> #include <algorithm> // C++ program to demonstrate working of `std::binary_search` algorithm int main() { int arr[] = { 4, 6, 8, 10, 15 }; int target = 10; if (std::binary_search(std::begin(arr), std::end(arr), target)) { std::cout << "Element found in the array"; } else { std::cout << "Element not found in the array"; } return 0; } |
Output:
Element is found at index 3
2. Binary Search in Java Collections
In Java, we can use the 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 std::binary_search
, which returns true on success, Arrays.binarySearch()
returns the search key index if it is contained in the array; otherwise, a negative value is returned. If a sorted array is not passed to it, the results are undefined.
The following Java program demonstrates its usage on a sorted integer array:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
import java.util.Arrays; // Java program to demonstrate working of `Arrays.binarySearch()` method class Main { public static void main(String[] args) { int[] A = { 4, 6, 8, 10, 15 }; int key = 10; int index = Arrays.binarySearch(A, key); if (index >= 0) { System.out.println("Element is found at index " + index); } else { System.out.println("Element not found in the array"); } } } |
Output:
Element is found at index 3
You can also implement the binary search algorithm, as discussed in detail in the following post:
Binary Search Algorithm – Iterative and Recursive Implementation
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)