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:

  1. The median/middle value is found and the pointer is set there, which in this case is 6.
  2. The target of 8 is compared to 6. Since 6 is smaller than 8, the target must be in the higher half.
  3. 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.
  4. 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.

Share this:

Connect with us

Email Newsletter

Join thousands of others with our weekly newsletter

Resources
The 4th Era of IT Infrastructure: Superconverged Systems
The 4th Era of IT Infrastructure: Superconverged Systems:
Learn the benefits and limitations of the 3 generations of IT infrastructure – siloed, converged and hyperconverged – and discover how the 4th...
Approaches and Benefits of Network Virtualization
Approaches and Benefits of Network Virtualization:
Businesses today aspire to achieve a software-defined datacenter (SDDC) to enhance business agility and reduce operational complexity. However, the...
Free E-Book: Public Cloud Guide
Free E-Book: Public Cloud Guide:
This white paper is for leaders of Operations, Engineering, or Infrastructure teams who are creating or executing an IT roadmap.
Free Tool: Virtual Health Monitor
Free Tool: Virtual Health Monitor:
Virtual Health Monitor is a free virtualization monitoring and reporting tool for VMware, Hyper-V, RHEV, and XenServer environments.
Free 30 Day Trial – Turbonomic
Free 30 Day Trial – Turbonomic:
Turbonomic delivers an autonomic platform where virtual and cloud environments self-manage in real-time to assure application performance.