NOTE: This is still on construction.
One of the most important algorithm in the world.
It allows us to quickly find a number in a sorted array of numbers. It is a kind of search where we reduce the search space into half at each comparison. We are able to reduce the subspace in half because the array is sorted and that is a preconditioned .
If we have to find an element x in the given sorted array using binary search, we can come up with three cases for the location of the element x;
Given that A[mid] is the element at the middle portion of the array
CASE 1: x==A[mid]
CASE 2: x<A[mid]
CASE 3: x>A[mid]
Since mid is the middle location, mid= (L+R)/2
Here L= 0, R= N-1, where N is the size of the array.
But there is a problem with this statement, although it will work in most cases but taking (L+R) for L and R being a very large number may lead to overflow and return us the wrong value.
To overcome this we may use mid= (L + ((R-L)/2))
So, with the above cases we can come with a BinarSearch function as
To visualize the Binary Search, you can refer to following link
https://www.cs.usfca.edu/~galles/visualization/Search.html
