What is binary Search algorithm?
A binary search algorithm is used to find the position of a particular value contained in a sorted array. This search algorithm, which works on the principle of divide and overcome, can be quite fast, but the limitation is that the data must be in a sorted form. It starts by searching in the middle of the array and processes the first lower or upper half of the sequence. If the median value is lower than the target value, it means that the search has to go higher, if not then it has to look at the descending part of the array.
A binary search is also known as a half-interval search or a logarithmic search.
A binary search is a quick and efficient way to find a certain target value from a set of ordered elements. By starting in the middle of the sorted list, it can effectively cut the search space in half by determining whether to increase or decrease the list based on the median relative to the target value.
For example with a target value of 8 and a search range from 1 to 11:
The middle / middle value is found and the pointer is placed there, which is 6 in this case.
The goal of 8 is compared to 6. Since 6 is less than 8, the goal must be in the higher half.
The pointer is moved to the next value (7) and compared with the target. It's smaller, so the pointer moves to the next higher value.
The pointer is now at 8. Compare this to the target, it is an exact match, so the target has been found.
In the binary search, the target only had to be compared with three values. Compared to a linear search, it would have started from the first value and moved up, with the goal having to be compared to eight values. A binary search is only possible with an ordered set of data; If the data were randomly arranged, a linear search would produce results all the time, while a binary search would likely get stuck in an infinite loop.