Binary Search Algorithm - Computerphile

Back to basics as Dr Mike Pound explains a simple but incredibly useful algorithm, binary search.

#algorithm #ComputerScience

This video was filmed and edited by Sean Riley.

[craftmechanics]

I love teaching this to my students as a guessing game.

I will think of a number from 1 to 100 and give them 8 guesses, but after each guess tell them if their guess was correct or lower/higher.

After a few rounds of playing, most people figure out that the optimal strategy is guessing somewhere in the middle, and essentially discover the algorithm on their own.

After that, we implement the gussing game on a computer.

I find this a very fun way to learn about binary search.

[emrekantar]

These men make me feel as if I am in a coffee house with my best friends talking

[zlkkwiu]

Dr. Pound is excellent and entertaining as always. I found myself smiling and giggling throughout the whole video due to the way he handles his small mistakes and jokes around. Yet he also imparts wisdom!

[Gudsfralsare]

In these times when AI is all the hype, these are the videos we need. The fundamental algos from the 60's are here to stay and run the world.

[genelee]

I'd love to see a video explaining the concepts behind how the different sorting algorithms work (Heap, Merge, Shell, etc)

[KurtisRader]

The point made at 14:30 is arguably the most important part of this video. Specifically, it is less important to know how to write, from scratch, a particular algorithm than it is to know that different algorithms have different tradeoffs. Knowing how to pick the best algorithm (and data structures) for a particular situation is more important than being able to implement an algorithm on a whiteboard. One of my interview questions explores whether an applicant understands that there are many sorting and searching algorithms and the nature of the data being manipulated, and other constraints, is important in deciding which algorithm to use.

[konstantinrebrov]

We need more videos explaining in low level details how various common algorithms work, such as file I/O, B trees, image compression, files representation (PDF, audio, video, archive, ELF), Huffman coding, hashing algorithms, md5sum, dynamic programming. I mean walk through the pseudocode line by line explaining what it does, and draw the memory diagrams, like what is happening to the data, how the bits or bytes are stored, loaded, moved around.

[vatbub]

One thing to add: Once the data is sorted, and you need to add new data to it, binary search can actually tell you where you need to insert the new data in order to keep the data sorted. Therefore, the real issue is getting the data sorted in the first place (as mentioned in the video), but once it is sorted, binary search helps you find stuff fast and helps you keep your data sorted even when you modify it.

[traywor]

10:25 just wanna note here for anyone trying to implement this algorithm for very large arrays, be aware of the integer overflow. (l + r) // 2 will first calculate l + r and then try to divide it by two. however if your list is lets say 2/3rds of the size of your integer and if you then add l + r and l and r are quite large, then they will overflow. Then your m will be messed up and your binary search will be incorrect. And this is not a contrived scenario, there was this exact kind of bug in the java SDK, for 9 years!

I was actually surprised that Mike didn't mentioned this :O

[Richardincancale]

One of my favourite books from almost 50 years ago - Sorting and Searching by Donald E Knuth - tells you all you need to know!

[doomanime]

I can sit and hear Dr Mike Pound talking all day

[daveingerslev]

Finding theft (or damage) on CCTV footage is a fantastic real world use for binary search. As long as something visually changes (i.e. goes missing or gets broken), then it turns the task of watching the cause into a 5 min task instead of hours/unjustifiable.

[GordonjSmith]

This was great! It really highlighted the need for the development of 'logical' learning, and not just 'proceedual' or 'fact' learning. Actually a very 'key vlog', in all the excellent vlogs that have been made.

[olafurfo]

Currently doing my second year in computer science and you made me realize when I'd want to use BST in projects.
Sort in morning, many lookups throughout the day.
Makes so much sense but I hadn't realized it, Well done !!!

[SparkysWidgets]

I changed a linear search on a calibration step for a product on the production line to binary searching. This small change netted millions of minutes of production line weekly(test used to take minutes and we produced over 1million units a week) back to the CM. The main point being is it doesn't have to be a large data set it could be a small known dataset but that each takes time to search or in this case "test".

[robblake]

It's an excellent point to remember that sorting is O(n log n), wheras a linear search is O(n). Linear search could definitely prevail for a small number of lookups.

[agoatmannameddesire]

More Dr Pound videos on search / sorting!

[-parrrate]

for most problems, I prefer a strict L<=answer<R state and dividing until D=floor((R-L)/2) is 0;
why I see it as simpler:
if D is at least 1, there is M=L+D such that L<M<R. choosing it as either L or R is guaranteed to reduce the search space;
choice is easy too: if M is too big, pick it as next R, else as next L;
when D hits 0, L is guaranteed to be the answer;

[thuokagiri]

prof Pound is the Richard Feynman of Computer science

[coolwarfare]

Thank you this channel is going to save me before GCSEs