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)