C++ Program for Binary Search

In this article, you will learn and get code for searching for an element in an array using the binary search technique in C++ programming. Here are the approaches used:

Before going through the above programs, if you're not aware of the binary search technique, you can refer to binary search to understand its logic and algorithm.

Binary Search in C++

To search an element from an array using the binary search technique in C++ programming, you have to ask the user to enter any 10 elements for the array and then enter the element or number to be searched.

After searching the element using the binary search technique, if it is available in the list, display the position of the element. The following C++ program asks the user to enter any 10 array elements and an element to be searched. Here is the simple binary search program:

#include<iostream>
using namespace std;
int main()
{
    int i, arr[10], num, first, last, middle;
    cout<<"Enter 10 Elements (in ascending order): ";
    for(i=0; i<10; i++)
        cin>>arr[i];
    cout<<"\nEnter Element to be Search: ";
    cin>>num;
    first = 0;
    last = 9;
    middle = (first+last)/2;
    while(first <= last)
    {
        if(arr[middle]<num)
            first = middle+1;
        else if(arr[middle]==num)
        {
            cout<<"\nThe number, "<<num<<" found at Position "<<middle+1;
            break;
        }
        else
            last = middle-1;
        middle = (first+last)/2;
    }
    if(first>last)
        cout<<"\nThe number, "<<num<<" is not found in given Array";
    cout<<endl;
    return 0;
}

This program was built and runs under the Code::Blocks IDE. Here is the initial snapshot of the sample run:

binary search c++

Now enter any 10 numbers (in ascending order) as array elements, say 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10, and then a number that is going to be searched from the list, say 8. Here is the final snapshot of the sample run:

c++ binary search program

If the user enters 10 elements as 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, and the element to be searched as 8, the above program will run as follows:

Allow the user to define the size

This program allows the user to define the size of the array. It also doesn't care about the way the user enters the data, that is, either in ascending or random order. Because, after receiving all the numbers, we've created a block of code that sorts the list in ascending order (before performing the search operation). Then, as shown in the program below, ask for an element to be searched from the sorted list:

#include<iostream>
using namespace std;
int main()
{
    int len, i, arr[50], num, j, temp, first, last, middle;
    cout<<"Enter the Size: ";
    cin>>len;
    cout<<"Enter "<<len<<" Elements: ";
    for(i=0; i<len; i++)
        cin>>arr[i];
    // sort the array first
    for(i=0; i<(len-1); i++)
    {
        for(j=0; j<(len-i-1); j++)
        {
            if(arr[j]>arr[j+1])
            {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    // print the sorted array
    cout<<"\nThe New Sorted Array is:\n";
    for(i=0; i<len; i++)
        cout<<arr[i]<<" ";
    // now back to binary search
    cout<<"\n\nEnter Element to be Search: ";
    cin>>num;
    first = 0;
    last = (len-1);
    middle = (first+last)/2;
    while(first <= last)
    {
        if(arr[middle]<num)
            first = middle+1;
        else if(arr[middle]==num)
        {
            cout<<"\nThe number, "<<num<<" found at Position "<<middle+1;
            break;
        }
        else
            last = middle-1;
        middle = (first+last)/2;
    }
    if(first>last)
        cout<<"\nThe number, "<<num<<" is not found in given Array";
    cout<<endl;
    return 0;
}

Here is its sample run, supposing that the user enters the array size as 5 and its elements as 5, 1, 4, 2, and 3:

binary search c++ example

Now enter an element, say 4, to search it from the list, and print its position as shown in the output given below:

binary search program in c++

To learn more about sorting an array, you can follow and apply any of the below sorting methods in the program:

Binary search in C++, using user-defined functions

This program is created using a user-defined function, binSearRecFun(), that receives three arguments. The first is the array, the second is the number to be searched, and the third is the array's size.This function either returns the position of the element in the list or a value of 0 that indicates the number is not available in the list.

Before the binary search, there is also a function called sortArray() that sorts the given array in ascending order.

#include<iostream>
using namespace std;
void sortArray(int [], int);
int binSearchFun(int [], int, int);
int main()
{
    int len, i, arr[50], num, pos;
    cout<<"Enter the Size (max. 50): ";
    cin>>len;
    cout<<"Enter "<<len<<" Elements: ";
    for(i=0; i<len; i++)
        cin>>arr[i];
    // sort the array first
    sortArray(arr, len);
    // print the sorted array
    cout<<"\nThe New Sorted Array is:\n";
    for(i=0; i<len; i++)
        cout<<arr[i]<<" ";
    cout<<"\n\nEnter Element to be Search: ";
    cin>>num;
    // search element using binary search
    pos = binSearchFun(arr, num, len);
    if(pos==0)
        cout<<endl<<num<<" isn't available in the list";
    else
        cout<<endl<<num<<" is available at Position "<<pos;
    cout<<endl;
    return 0;
}
void sortArray(int arr[], int len)
{
    int i, j, temp;
    for(i=0; i<(len-1); i++)
    {
        for(j=0; j<(len-i-1); j++)
        {
            if(arr[j]>arr[j+1])
            {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}
int binSearchFun(int arr[], int num, int len)
{
    int first, last, middle;
    first = 0;
    last = (len-1);
    middle = (first+last)/2;
    while(first <= last)
    {
        if(arr[middle]<num)
            first = middle+1;
        else if(arr[middle]==num)
            return (middle+1);
        else
            last = middle-1;
        middle = (first+last)/2;
    }
    return 0;
}

Here is its sample run, supposing that the user enters the size as 6, its elements as 6, 1, 5, 2, 3, and 4, and the number to be searched as 4:

binary search example c++

Binary search in C++ using recursion

This program uses recursion (a function that calls itself) to search an element using the binary search technique.

#include<iostream>
using namespace std;
int binSearRecFun(int [], int, int, int);
int main()
{
    int i, arr[10], num, pos;
    cout<<"Enter 10 elements (in ascending order): ";
    for(i=0; i<10; i++)
        cin>>arr[i];
    cout<<"\nEnter element to be search: ";
    cin>>num;
    pos = binSearRecFun(arr, 0, 9, num);
    if(pos==0)
        cout<<endl<<num<<" is not available in the list";
    else
        cout<<endl<<num<<" is available at Position "<<pos;
    cout<<endl;
    return 0;
}
int binSearRecFun(int arr[], int first, int last, int num)
{
    int middle;
    if(first>last)
        return 0;
    middle = (first+last)/2;
    if(arr[middle]==num)
        return (middle+1);
    else if(arr[middle]>num)
        binSearRecFun(arr, first, middle-1, num);
    else if(arr[middle]<num)
        binSearRecFun(arr, middle+1, last, num);
}

Here is its sample run:

binary search using recursion c++

The same program in different languages

C++ Quiz


« Previous Program Next Program »


Liked this post? Share it!