Binary search is one of the highly efficient search algorithm with a complexity of log(n) as here we divide the target array to half n/2 each time till we get the target item , so for an array of size 8 . we get the element with in 3 operation.
Note that binary search can be carried out only for a sorted array so it wont be always the best algorithm to use.
For example , you have an unsorted array of unique element, to find a specific item using binary search , we first need to sort it. The best sorting algorithm complexity is O(nlogn) , after sorting we do binary search. This result in final complexity of nlogn + logn , and as nlogn is the higher term we drop logn , so final Big O is O(nlogn).
Instead if we just checked each element using a for loop , the complexity would have been just O(n) which was much better than O(nlogn).:
So how binary search works:
Assume we have an array sorted in ascending order:
[1,2,3,4,5,6,7,8]
Now we have to find index of ‘5’
Step 1:
so what we do is , first check the midIndex in the array for the element.
the mid index is rounded ((first index + last index)/2) ie (0+7)/2 = 3.5 = 3
so we check if array[3] is what we want , array[3] is 4 , so its not what we want
Step 2:
now we check if the target is on the left or right of the array ( this is because the array is a sorted array so we can guarantee the order of elements)
we see that as 5 > 4 , the element should be to the right of array[3]
so now we dont want to look at the elements from 0–3 , so we set first Index to midIndex + 1, last index remains the same.
(if it was on the left. ie target < array[mid] then first index remains the same , and last index becomes mid-1 as we dont have to check elements to the right of the sorted array)
step 3:
now repeat step 1 and 2 : ie :
now find the new midIndex ((first index + last index)/2) ie (4+7)/2 = 5.5 = 5
check mid element array[mid] === target return else set first or last index