#90 Binary Search
One of the most fundamental algorithms in computer science.
Kopec Explains Software · David Kopec, Rebecca Kopec
Audio is streamed directly from the publisher (pdcn.co) as published in their RSS feed. Play Podcasts does not host this file. Rights-holders can request removal through the copyright & takedown page.
Show Notes
Binary search is an algorithm for finding an item in a sorted data set. It requires that all of the items in the data set be of the same data type and comparable to one another. In other words, the data type needs to have a defined "order." Binary search is orders of magnitude more efficient than its chief alternative, linear search, which is just an in-order search of every item in a data set. Binary search works by continuously reducing the search space by half. A binary search can find an item in a data set in a maximum of log(number of items in the data set) operations where log is base 2. We explain this simple but efficient fundamental computer science algorithm and the downside of requiring that a data set be sorted.
Show Notes
Follow us on Twitter @KopecExplains.
Theme “Place on Fire” Copyright 2019 Creo, CC BY 4.0
Find out more at http://kopec.live