C++ Program for Binary Search

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

  • Simple binary search program
  • Allow user to define array size and sorts before searching
  • Using user-defined function
  • Using recursion

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

Binary Search in C++

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

After searching the element using binary search technique, if it is available in the list, then display the position of the element. Following C++ program asks from user to enter any 10 array elements and an element to be search. 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 build and run under Code::Blocks IDE. Here is the initial snapshot of 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, 10 and then a number that is going to be search from the list, say 8. Here is the final snapshot of sample run:

c++ binary search program

If user enters 10 elements as 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 and element to be search as 8, then dry run of above program goes like:

  • 10 elements gets stored in the array arr[] in a way that, arr[0]=1, arr[1]=2, arr[2]=3, and so on
  • The number to be search say 8 gets initialized to num. Therefore, num=8
  • Initially first=0 and last=9
  • (first+last)/2 or 0+9/2 or 4 gets initialized to middle. Therefore middle=4
  • Because the value of first (0) is less than the value of last (9), so the condition of while loop evaluates to be true. Therefore program flow goes inside the loop
  • Checks whether arr[middle]<num evaluates to be true or not. On putting the value of variables middle and num, arr[4]<num or 5<8 evaluates to be true. Therefore program flow goes inside the if block and middle+1 or 4+1 or 5 gets initialized to first
  • Because, the condition of if block evaluates to be true, therefore else if and else block's statement(s) will not get executed.
  • At last, middle = (first+last)/2 or middle = (5+9)/2 or middle=7
  • Program flow goes back to the condition of while loop. The condition first <= last or 5<=9 again evaluates to be true, therefore again program flow goes inside the loop
  • Checks the condition of if block, that is arr[middle]<num evaluates to be true or not, that is arr[7]<num or 8<8 evaluates to be false. Therefore, program flow goes to else if block, and checks its condition
  • The condition arr[middle]==num or 8==8 evaluates to be true. Therefore program flow goes inside this else if block and executes its statements
  • That is, prints the position of number. Because the number is found at index number 7. Therefore I've printed its position as 8, since indexing in arrays starts from 0, not from 1
  • After printing the position of element, use the break keyword to break out from the while loop
  • After exiting from the while loop, checks the condition using if block, that is whether first's value is greater than the value of last or not
  • If condition evaluates to be true, then print a message saying that the number is not found in the list

Allow User to Define Size

This program allows user to define the size of array. It also doesn't cares about the way user enters the data, that is, either in ascending or in 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). And then ask to enter an element to be search from the sorted list as shown in the program given below:

#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 user enters the array size as 5 and its element as 5, 1, 4, 2, 3:

binary search c++ example

Now enter an element say 4 to search it from the list and prints 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 method in the program:

Using user-defined Function

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

A function named sortArray() is also implemented here to sort the given array in ascending order before going for the binary search.

#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 user enters size as 6, its elements as 6, 1, 5, 2, 3, 4, and the number to be search as 4.:

binary search example c++

Using Recursion

This program uses recursion (function that calls itself) to search an element using 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++

Same Program in Other Languages

C++ Online Test


« Previous Program Next Program »



Like/Share Us on Facebook 😋