Articles

C++ program to search an element using binary search method

C++ program to search an element using binary search method

In this chapter of C++ program tutorial out task is: 

  • Write a C++ program to search an element using binary search in array

C++ program to search an element using binary search

Below is the C++ program to search an element using binary search.

#include<iostream>
using namespace std;
int binarySearch(int arr[], int low, int high , int x)
{
    if(high >= low){
        int mid = (high + low)/2;
        if(arr[mid] == x){
            return mid;
        }
        if(arr[mid] > x){
            return binarySearch(arr, low, mid-1, x);
        }
        return binarySearch(arr, mid+1, high, x);
    }
    return -1;
}
int main()
{
    int n,i,x;
    cout<<"Enter the number of elements\n";
    cin>>n;
    int arr[n];
    cout<<"Enter the elements of the array in sorted order\n";
    for(i=0;i<n;i++){
        cin>>arr[i];
    }
    cout<<"Enter the element to be searched\n";
    cin>>x;
    int result = binarySearch(arr, 0, n-1, x);
    if(result == -1){
        cout<<"Element is not present in the array"<<endl;
    }
    else
        cout<<"Element is present in the index: "<<result<<" of the array"<<endl;
    return 0;
}

OUTPUT :

Enter the number of elements
10
Enter the elements of the array in sorted order
7 9 10 13 15 16 18 32 65 72
Enter the element to be searched
16

 

Element is present in the index: 5 of the array
 
EXPLANATION :
In the above program:
  • By calling the function binarySearch the array , the lowest index, the highest index and the element to be searched are passed.
  • Then inside the function the middle value of the array is calculated and checked whether it is the searched element or not
  • if the middle element is not the searched element the it checked whether the number to be searched is smaller or greater than than the middle element
  • If the element is smaller then the left side of the middle element is checked and if it is greater the the right side of the middle element is checked.
  • This process goes on until the middle element is found through recursion and the index element is returned

NOTE: THE ARRAY MUST BE SORTED.

cpp program to search an element using binary search methodWORKING :

arr[] = {7,9,10,13,15,16,18,32,65,72}

n = 10

x = 16

1st iteration

if(10 >= 0)    // true

mid = (high + low /2)   //  (9 + 0)/2 = 4 [as mid is in integer data type]

if(arr[4] == 16)   //  false

if(arr[4]>16) // false

return (arr , 5 , 9 , 16)

2nd iteration

if(10 >= 5)    // true

mid = (high + low /2)   //  (10 + 5)/2 = 7 [as mid is in integer data type]

if(arr[7] == 16)   //  false

if(arr[7]>16) // false

return (arr , 5 , 6 , 16)

3rd iteration

if(6 >= 5)    // true

mid = (high + low /2)   //  (6 + 5)/2 = 5 [as mid is in integer data type]

if(arr[5] == 16)   //  true

return 5

The recursion ends with this.

 

Time complexity:

O(logn)

 

You can see the above code execution and output in codeblocks IDE:  

cpp program to search an element using binary search method codeblocks ide code

 


CPP Programs

Would you like to see your article here on tutorialsinhand. Join Write4Us program by tutorialsinhand.com

About the Author
Sayantan Bose
A coder who learns from mistakes
Page Views :    Published Date : Aug 31,2020  
Please Share this page

Related Articles

Like every other website we use cookies. By using our site you acknowledge that you have read and understand our Cookie Policy, Privacy Policy, and our Terms of Service. Learn more Got it!