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
   {
      cout<<"Element not found";
   }
   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)