Articles

# 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. WORKING :

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 == 16)   //  false

if(arr>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 == 16)   //  false

if(arr>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 == 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 Programs

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