Join the social network of Tech Nerds, increase skill rank, get work, manage projects...
 
  • Binary search in C++

    • 0
    • 1
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 780
    Comment on it

    If you want to find the presence of a element in a given sorted range, then you can use the binary_search function defined in the STL algorithm.

    The range should be sorted in ascending order to perform binary search.

    It returns true if element is found within the range, else returns false.

    Template for the function binary_search

     bool  binary_search (RandomIterator first, RandomIterator last, const T& val);
    

    About parameters
    first
    RandomIterator for the initial position of the range which is included in the range.

    last
    RandomIterator for the final position which it not included in the range.

    val
    value to be searched within the range.

    A sample program using binary_serach

    #include <iostream>
    #include <algorithm>
    #include <vector>
    
    using namespace std;
    
    int main()
    {
            vector <int> v;
            v = {48,9,2,7,83,6,6,67,5};
    
            //printing the elements in the range
            cout << "Before Sorting : ";
            for ( int i: v) cout << i << " ";
            cout << endl;
    
            //applying sort function in the range
            sort(v.begin(),v.end());
    
            //printing the elements in the range
            cout << "After Sorting  : ";
            for ( int i: v) cout << i << " ";
            cout << endl;
    
            //binary search for 7
            if (binary_search(v.begin(),v.end(),7)) {
                    cout << "7 found in the range" << endl;
            } else {
                    cout << "7 not found in the range" << endl;
            }
    
            //binary search for 3
            if (binary_search(v.begin(),v.end(),3)) {
                    cout << "3 found in the range" << endl;
            } else {
                    cout << "3 not found in the range" << endl;
            }
    
            return 0;
    }
    

    Use C++11 mode ( if you want to use range-based for loops)

    Output of the above program

    Before Sorting : 48 9 2 7 83 6 6 67 5 
    After Sorting  : 2 5 6 6 7 9 48 67 83 
    7 found in the range
    3 not found in the range
    

    Time complexity for binary search is logarithmic in between the range.

 0 Comment(s)

Sign In
                           OR                           
                           OR                           
Register

Sign up using

                           OR                           
Forgot Password
Fill out the form below and instructions to reset your password will be emailed to you:
Reset Password
Fill out the form below and reset your password: