codescracker
c++

C++ Program for Binary Search



« Previous Program Next Program »

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:

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:

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 »



© Copyright 2021. All Rights Reserved.

CodesCracker