Binary Search Program in C++

This article will teach you how to use C++’s binary search algorithms to find a specific element in an array, along with sample code. These were the methods:

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

If you are unfamiliar with the binary search approach before running the above program, you may refer to a binary search to learn more about its logic and algorithm.

What is Binary Search in C++?

In C++ programming, you must first ask the user to input any items for the array before entering the element or number to be searched. This is known as the binary search strategy.
If the element is found in the list using the binary search approach and is present, the element’s location will be shown. The user is prompted to enter up to 10 array elements and a search element in the following C++ software. This is a straightforward binary search program:

Code Implementation:

#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;
}

Input: 2 3 5 6 8 9 10 15 16 25 89 110
           89
Output:
Enter 10 Elements (in ascending order): 
Enter Element to be Search: 
The number, 89 is not found in given Array

Algorithm of Binary Search in C++

  • Declare the variables, then enter an array’s elements in any order (ascending or descending).
  • The array element listings should be split in half.
  • Now compare the target elements with the array’s middle element. Additionally, if the middle element’s value matches the target element’s value, return the middle element’s location and the search is finished.
  • We search the elements in the lower half of an array if the target element is less than the middle element.
  • We must seek the target element in the bigger half of the array if it is larger than the middle element.
  • Up until the requested element is not present in the sorted array, steps 4, 5, and 6 will be repeatedly performed.

Explanation of Binary Search in C++:

  • If a user types in 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, and the element to be searched is element number 8, the following program will behave as follows during a dry run:
  • The array arr[] stores 10 elements in such a way that arr[0]=1, arr[1]=2, arr[2]=3, and so on.
  • The initialization of num is 8, which is the searchable number. Hence, num=8.
  • Middle is initialized to first=0 and last=9 (first+last)/2 or 0+9/2 or 4. consequently middle=4
  • The while loop’s condition is evaluated to be true since first’s value (zero) is smaller than last’s (nine). Consequently, program flow occurs inside of the loop.
  • Determines if arr[middle] is false. As a result, the program flow enters the else if block and verifies its state.
  • The evaluation of the condition arr[middle]==num or 8==8 is true. As a result, the sentences inside this if else block are executed.
  • Prints the number’s location, in other words. due to the fact that the number is located at position 7. As a result, I reported its position as 8, as array indexing begins at 0, not at 1.
  • To exit the while loop after reporting the element’s location, use the break keyword.
  • Once the while loop has finished, the if block is used to determine whether the value of first is greater than the value of the last.
  • If the condition is true, print a message indicating so.
  • If the condition is true, print a message informing the user that the specified number cannot be found in the list.

Binary Search programs in C++

Check the following Binary search program code by using the different method in C++

Method 1: Allow the User to Define the Size

The user can specify the array size with this program. Additionally, it doesn’t care if the user enters the data in ascending or random order. Because we wrote a piece of code that sorts the list in ascending order after getting all the integers (before performing the search operation). then request that you select an element to search for from the sorted list, as seen in the following program:
Code Implementation:

#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;
}

Input: 5
2 3 5 8 9
5

Output: Enter the Size: Enter 5 Elements: 
The New Sorted Array is:
2 3 5 8 9

Enter Element to be Search:
The number, 5 found at Position 3

Method 2: Using user-defined Function

BinSearRecFun(), a user-defined function that takes three parameters, is used to create this program. The array is the first item, followed by the number to be searched and the array’s size. This function either returns the element’s position in the list or 0 to denote that the requested number is not present in the list.
Before beginning the binary search, the provided array is sorted in ascending order using a method called sortArray().

Code Implementation:

#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;
}

Input: 5
10 20 30 40 50
30

Output: Enter the Size (max. 50): Enter 5 Elements:
The New Sorted Array is:
10 20 30 40 50 

Enter Element to be Search:
30 is available at Position 3

Method 3: Using Recursion

This program uses recursion (a function that calls itself) to do a binary search on an element.

Code Implementation:

#include <bits/stdc++.h>
using namespace std;
 
int binarySearch(int arr[], int l, int r, int x)
{
    if (r >= l) {
        int mid = l + (r - l) / 2;
 
        if (arr[mid] == x)
            return mid;
 
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);
 
        return binarySearch(arr, mid + 1, r, x);
    }
 
    return -1;
}
 
int main(void)
{
    int arr[] = { 20, 30, 40, 100, 400 };
    int x = 30;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, 0, n - 1, x);
    (result == -1)
        ? cout << "Element is not present in array"
        : cout << "Element is present at index " << result;
    return 0;
}

Output: Element is present at index 1

Time Complexity of Binary Search in C++

Scenario Time Complexity
Best Case O(1)
Average Case O(logn)
Worst Case O(logn)

Best Case Complexity – In a binary search, the best case scenario is when the searchable element is discovered in the first comparison, or when the first middle element is in fact the searchable element. Binary search has a best-case temporal complexity of O(1).

Average Case Complexity – For a binary search, the average case time complexity is O(logn).

Worst Case Complexity – The worst case scenario for binary search is when we have to continuously narrow the search space until there is just one element. Binary search has a worst-case temporal complexity of O(logn).

Space Complexity
The Space complexity for coding binary search program in c++ is O(1).

Tips: On sorted array elements, binary search can be applied. We must first sort the list elements if they are not already organized in a sorted fashion.

Conclusion
All kinds of approaches to binary search in C++ can be discussed correctly in this article. We hope this article enhances your knowledge. Many competitive programming questions will use binary search algorithms to solve difficult problems.

Other C++ Programs.

C++ Program to Add Two Numbers
C++ Program to Reverse a Number
C++ program for heap sort
Bubble Sort in C++ with Program Code and Example
Hello world program in C++
Prime Number Program in C++
Factorial Program in C++

Leave a Reply

Your email address will not be published. Required fields are marked *