4 ms·
Binary Search. (And its antithesis, exponential growth.) In my opinion it is the single most important piece of computer science insight with the constraint th
by mikorym 7y ago
Binary Search. (And its antithesis, exponential growth.)
In my opinion it is the single most important piece of computer science insight with the constraint that you only have less than an hour.
I often use binary search as a sort of thought experiment into whether something is "obvious" or not. As a child, I would say exponential growth is the one thing that I developed no intuition for between the age of 1–11. Even now, I regard exponentiation as the one really fundamental thing you possibly won't discover or have intuition for on your own and first see it at school (in contrast to addition or multiplication maybe). And even then, you have to accept exponential growth before you start to "understand" it. Maybe if you are Gauss, it's different for you...
Binary search is also a nice way of explaining counting, specifically the combinatorics thereof. You can write down the numbers [0,...,2^n-1] in binary, and then show how when you halve each time with binary search, you actually are just checking the leading bit (and then discarding it). When you have discarded all the bits in that way, then you have found the position you are looking for.
- nurettin 7y agoThis is the first thing I talk about when someone asks me what computer science teaches a person and how it relates to real world. It covers a practical example and lets you touch on topics like algorithmic complexity. And it takes 5 minutes to explain. So I fill the rest of the time by demonstrating a simple sorting algorithm on paper and I finish off by drawing a simple maze and solving it with breadth first search by marking squares with numbers.
- notelonmusk 7y agoSince you mentioned sorting 'on paper', here's the sorting algorithm you'd use as a human sorting papers :) https://www.quora.com/What-is-the-best-manual-sorting-algorithm-E-g-if-you-had-a-stack-of-papers-that-you-wanted-to-sort-alphabetically-what-would-be-the-most-efficient-way-to-do-it-What-if-you-were-okay-with-them-being-off-by-one-or-two-from-their-sorted-position https://www.quora.com/What-is-the-best-manual-sorting-algori...
- rikkus 7y agoI'm currently teaching my child binary search. She thinks we're just having fun playing "Guess Who?"