Go offline with the Player FM app!
#90 Binary Search
Manage episode 325939624 series 2709740
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
140 episodes
Manage episode 325939624 series 2709740
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
140 episodes
All episodes
×Welcome to Player FM!
Player FM is scanning the web for high-quality podcasts for you to enjoy right now. It's the best podcast app and works on Android, iPhone, and the web. Signup to sync subscriptions across devices.