Binary Search in C++ STL and Java Collections

Binary Search in C++ STL and Java Collections

This post is about describing binary search in C++ STL and Java Collections. Binary search is a search algorithm based on dividing the search area into half and then performing required operations. If the results are still not found, the search area is halved again to have the search space as small as possible so that the element that is being searched can be easily found. 

Binary Search in C++ STL

In C++, the STL library has a header named “algorithm” that has a function named std::binary_search defined in it. If a sorted array needs to be binary searched, then the starting and ending address of the array needs to be supplied to this function, or more generally, the iterators to the starting and ending positions of a sorted sequence and return true if the required value is found, if not, returns false.

This type of search takes O(logn) running time where n is the number of elements and is quite efficient for searching large sorted arrays. The program provided below displays the use of std::binary_search function of the header file “algorithm” as follows:

// Program to illustrate binary search in STL

#include<iostream>

// header file that includes the definition for binary_search() function
#include<algorithm>
int main(){

    // int array with 5 elements
    int array[]={1,2,3,4,5};

    // element to be searched in the given array
    int element_to_be_searched=4;

    // if condition includes a call to binary_search() function
    if(std::binary_search(array, array+5, element_to_be_searched)){
        std::cout<<element_to_be_searched<<" found in the given array.";
    }
    else{
        std::cout<<element_to_be_searched<<" not found in the given array.";
    }
    return 0;
}

Output:

4 found in the given array.

Binary Search in Java Collections

In Java, a built-in function named binarySearch() is defined in the Arrays class specified in java.util package. This function takes in an array or ranges it as a parameter and performs a binary search on it to find the target element. If found, this function returns the index of the element in the array, otherwise returns false stating the absence of the said element, unlike the std::binary_search function of the algorithm header file of the STL library which returns true if the target element is found, otherwise returns false.

This function is overloaded for all primitive types, and can even sort an object array using a comparator. The program provided below displays the use of binarySearch() function as follows:

// Program to illustrate binary search in collections

// Arrays class of java.util package contains binarySearch() function
import java.util.Arrays;
public class binary_search_in_collections{
    public static void main(String[] args) {

        // int array of 5 elements
        int[] arr={1,2,3,4,5};

        // element to be searched
        int element_to_be_searched=2;

        // if-condition involves call to binarySearch which returns a non-negative integer if element to be searched is found
        if(Arrays.binarySearch(arr, element_to_be_searched)>=0){
            System.out.println(element_to_be_searched+" found in the given array.");
        }
        // returns a negative integer if element to be searched is not found
        else{
            System.out.println(element_to_be_searched+" not found in the given array.");

        }
    }
}

Output:

2 found in the given array.