Binary search explanation

Binary search is one of the best searching technique which is most efficient among other searching techniques. Binary search works on the sorted elements and as the elements are sorted so its easy to iterate by finding the mid element continously.

Pre-requisite for binary search is the array or Data structure should be sorted. 

Working of Binary Search : 

There are two index with the help of which we will iterate on the array to search the specific element. Left and Right in which left starts from 0 and right starts from N-1.

then the mid of array is computed

mid=left+right/2;

if mid is equal to target element then break

else if mid element is greater than target element, which roughly means that the target element is between 0 and mid-1 that's why right is updated with mid-1

else mid element is lesser than target element which means that the target element is between mid+1 and right.

So like this we are continously finding the mid for every left and right index and will get the target.

Example : 

arr={1,4,5,8,9,15};

target = 4.

Iteration 1 : left=0 and right = 5.

mid= 0+5/2=2

arr[2]=5

so, right would be mid-1 as target<arr[mid]

Iteration 2 : left=0 and right=1

mid= 0+1/2 = 0

arr[0]=1

so, left would be mid+1 as target>arr[mid]

Iteration 3 : left 1 and right =1

mid=1+1/2=1

arr[1]=4

Hence 4==4 we got it on 2nd index. Element found.

Why it is efficient than linear search 

Normally if you are searching in 10 elements then efficiency cannot be seen but when you are searching in a large dataset then you can find the efficiency that how faster binary search is.

Example if you are searching in 100000 elements 

So first it will does half and check where the element stands and then accordingly within 10-20 iteration it will find the target.

whereas linear search taken N number of iterations to search it.