Binary Search
Definition - What does Binary Search mean?
A binary search algorithm is used to find the position of a specific value contained in a sorted array. Working with the principle of divide and conquer, this search algorithm can be quite fast, but the caveat is that the data has to be in a sorted form. It works by starting the search in the middle of the array and working going down the first lower or upper half of the sequence. If the median value is lower than the target value, that means that the search needs to go higher, if not, then it needs to look on the descending portion of the array.
A binary search is also known as a half-interval search or logarithmic search.
Techopedia explains Binary Search
A binary search is a quick and efficient method of finding a specific target value from a set of ordered items. By starting in the middle of the sorted list, it can effectively cut the search space in half by determining whether to ascend or descend the list based on the median value compared to the target value.
For example, with a target value of 8 and a search space of 1 through 11:
- The median/middle value is found and the pointer is set there, which in this case is 6.
- The target of 8 is compared to 6. Since 6 is smaller than 8, the target must be in the higher half.
- The pointer is moved to the next value (7) and compared to the target. It is smaller, therefore the pointer moves to the next higher value.
- The pointer is now on 8. Comparing this to the target, it is an exact match, therefore the target has been found.
Using binary search, the target only had to be compared to three values. Compared to doing a linear search, it would have started from the very first value and moved up, needing to compare the target to eight values. A binary search is only possible with an ordered set of data; if the data is randomly arranged, then a linear search would yield results all the time while a binary search would probably be stuck in an infinite loop.
