Episode 542
Binary search algorithm
Mon, 2018-Oct-29 00:31 UTC
Length - 2:52
Direct Link
Welcome to featured Wiki of the Day where we read the summary of the featured Wikipedia article every day.
The featured article for Monday, 29 October 2018 is Binary search algorithm.
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array. Even though the idea is simple, implementing binary search correctly requires attention to some subtleties about its exit conditions and midpoint calculation.
Binary search runs in logarithmic time in the worst case, making O(log n) comparisons, where n is the number of elements in the array, the O is Big O notation, and log is the logarithm. Binary search takes constant (O(1)) space, meaning that the space taken by the algorithm is the same for any number of elements in the array. Binary search is faster than linear search except for small arrays, but the array must be sorted first. Although specialized data structures designed for fast searching, such as hash tables, can be searched more efficiently, binary search applies to a wider range of problems.
There are numerous variations of binary search. In particular, fractional cascading speeds up binary searches for the same value in multiple arrays. Fractional cascading efficiently solves a number of search problems in computational geometry and in numerous other fields. Exponential search extends binary search to unbounded lists. The binary search tree and B-tree data structures are based on binary search.
This recording reflects the Wikipedia text as of 00:31 UTC on Monday, 29 October 2018.
For the full current version of the article, go to http://en.wikipedia.org/wiki/Binary_search_algorithm.
This podcast is produced by Abulsme Productions based on Wikipedia content and is released under a Creative Commons Attribution-ShareAlike License.
Visit wikioftheday.com for our archives, sister podcasts, and swag. Please subscribe to never miss an episode. You can also follow @WotDpod on Twitter.
Abulsme Productions produces the current events podcast Curmudgeon's Corner as well. Check it out in your podcast player of choice.
This has been Joey. Thank you for listening to featured Wiki of the Day.
|
|
Buy WotD Stuff!!
