Binary Search

It works on the principle of divide and conquer. You are given an array(In Sorted order). Now consider that the number that you are trying to search is at the last position(which is the worst case in Linear Search.) but with the binary search, you can do that in lesser time. Below is an Example of Binary Search(We will use C++):

Example:

void binarySearch(int arr[], int size, int element) {
  int first=0;
  int last=size-1;
  int middle=(first+last)/2;
  while(last>=first)
  {
    if(arr[middle]<element){ first=middle+1; }
    else if(arr[middle]==element){ cout<<"Element found at position: "<<middle+1; break; }
    else{ last=middle-1; }
    middle=(first+last)/2;
  }
}

int main()
{
clrscr();
int arr[50], size, x;
cout<<"Enter the size of array: ";
cin>>size;
cout<<"Enter the Elements of Array: \n";
for(int i=0;i<size;i++)
cin>>arr[i];
cout<<"Enter the Element to Search: ";
cin>>x;
binarySearch(arr,size,x); //Calling the BinarySearch Function
return 0;
}

Output:

Enter the size of array: 3
Enter the Elements of Array: 
2 4 6
Enter the Element to Search: 6
Element found at position: 3