Saturday, June 19, 2021
Home coding Write a program to search an element using binary search.

# Write a program to search an element using binary search.

Given a sorted integer array we have to search an element in an array using binary search.

Binary search is only applicable for sorted array.

Example:

``````input:arr[]={1,2,3,4,5} k=3
output:true``````

Logic:

``````Step 1-find the mid point of array.
step 2-if element at mid is smaller than we will start searching on left side.
step 3-if it is greater than mid ,then start searching on right side.``````

Code-

```#include <iostream>
using namespace std;
int binarySearch(int arr[], int low, int high, int key)
{
int mid;
if(high >= low)
{
mid = (low + high)/2;
if(arr[mid] == key)
{
return mid+1;
}
else if(arr[mid] < key)
{
return binarySearch(arr,mid+1,high,key);
}
else
{
return binarySearch(arr,low,mid-1,key);
}

}
return -1;
}

int main()
{
int num[10] = {10, 2, 7, 5, 9, 12};
int key;
int loc=-1;

cout<<"Enter the number that you want to search: ";
cin>>key;

loc = binarySearch(num, 0, 6, key);

if(loc != -1)
{
cout<<key <<" found in the array at the location: "<<loc;
}
else
{
}
return 0;
}

```

Output:

```Enter the number that you want to search: 2
2 found in the array at the location: 2```

Time complexity:0(logN)

Space Complexity:O(1)