Binary Search

 Binary Search

Binary Search is a searching technique that search the required element in the sorted array.

It searches the required element in the half part of array based on the condition:

•  if middle element is the element user want to search then it will return the index of middle element.

• if middle element is greater than the target element then it will search in the left part of the array and will not search in the right half.

• if middle element is smaller than the target element then it will search in the right part of the array and will not search in the left half.

• if targeted element is not found in the array then we can simply return -1.

#include <iostream>

using namespace std;

int binarySearch(int arr[],int target,int n) { int low = 0,high = n-1; while(low<=high) { int mid = low + (high-low)/2; //finding the middle element if(arr[mid] == target) // checking if middle is equal to target return mid; else if(arr[mid]>target) high = mid-1; // searching in the left half else low = mid+1; //searching in the right half } return -1; }

int main() { int size; cout<< "Enter array size" << endl; cin>> size;

int arr[100],ele; cout<<"Enter array elements in sorted order"<<endl; for(int i=0;i<size;i++) { cin>>arr[i]; } cout<<"Enter the element you want to search"<<endl; cin>>ele; int ind = binarySearch(arr,ele,size); if(ind != -1) cout<<"Element found at position: "<<ind+1; else cout<<"Element not found in the array"; return 0; }

Time Complexity:

Best Case: O(1) //if middle element is the target element

Worst Case: O(logn) //element will be searched in the half of the array.

Average Case: O(logn)