filmov
tv
Binary Search Algorithm: Explanation and Python Tutorial
Показать описание
Binary search is the powerhouse of computer science... Pretty much. One of the most basic introductory concepts in algorithms is binary search, but don't be fooled, binary search is incredibly powerful. Basically, the idea behind it is you are given a (sorted) list of items, you can leverage the sorted-ness to determine where something is much faster than scanning the whole list.
Let's start with guessing a random number between 1 to 10. One way we could do it is to scan the entire list one at a time.. 1, 2, 3... until we get to the right number. But, this is slow! Instead, we can use the computer's feedback to cut down the possibility space in half every time, if we start guessing from the middle. This is what we call divide-and-conquer. The whole gist of binary search is based on this principle.
In a sorted list, we can first guess the middle element and after receiving feedback, we can narrow down the possibilities to either side of that element (if it's not that element itself). We repeat this process until we have either found the element or determined that it's not present.
If our list is "n" elements long, binary search only takes a maximum of log(n) tries to find the answer, whereas linear (naive) search takes a maximum of n tries and average of n/2 tries. This means.. for a list of 1000 items, binary search takes 10 tries when linear search takes on average 500, but could take up to 1000 (and that's assuming the value you're looking for is in the list)!!
Understood? Good. Now we'll code it up and I'll show you exactly how much faster binary search is, compared to naive search!
Feel free to leave any questions.
Thanks for watching everyone!
~~~~~~~~~~~~~~~~~~~~~~~~
Let's start with guessing a random number between 1 to 10. One way we could do it is to scan the entire list one at a time.. 1, 2, 3... until we get to the right number. But, this is slow! Instead, we can use the computer's feedback to cut down the possibility space in half every time, if we start guessing from the middle. This is what we call divide-and-conquer. The whole gist of binary search is based on this principle.
In a sorted list, we can first guess the middle element and after receiving feedback, we can narrow down the possibilities to either side of that element (if it's not that element itself). We repeat this process until we have either found the element or determined that it's not present.
If our list is "n" elements long, binary search only takes a maximum of log(n) tries to find the answer, whereas linear (naive) search takes a maximum of n tries and average of n/2 tries. This means.. for a list of 1000 items, binary search takes 10 tries when linear search takes on average 500, but could take up to 1000 (and that's assuming the value you're looking for is in the list)!!
Understood? Good. Now we'll code it up and I'll show you exactly how much faster binary search is, compared to naive search!
Feel free to leave any questions.
Thanks for watching everyone!
~~~~~~~~~~~~~~~~~~~~~~~~
0:02:20
Binary Search Algorithm in 100 Seconds
0:04:00
Binary search in 4 minutes
0:00:55
Binary Search animated
0:18:34
Binary Search Algorithm - Computerphile
0:10:04
Learn Binary Search in 10 minutes 🪓
0:06:51
How Binary Search Makes Computers Much, Much Faster
0:08:23
Binary Search examples | Successful search | Design & Algorithms | Lec-13 | Bhanu Priya
0:06:22
Algorithms: Binary Search
0:01:00
Binary search algorithm part 4 in java in telugu
0:04:16
Linear search vs Binary search
0:19:36
2.6.1 Binary Search Iterative Method
0:17:48
Binary Search in Java - Full Simple Coding Tutorial
0:23:30
7.2 What is Binary Search | Binary Search Algorithm with example | Data Structures Tutorials
0:08:56
Binary Search - A Different Perspective | Python Algorithms
0:14:23
Introduction to Binary Search (Data Structures & Algorithms #10)
0:12:45
What is binary search
0:16:25
Introduction to Binary Search
0:11:41
Binary Search Algorithm | C Programming Example
0:15:20
Binary Search Algorithm: Explanation and Python Tutorial
0:14:57
Binary Search Algorithm with step-by-step animations and examples | Study Algorithms
0:07:11
2.6.2 Binary Search Recursive Method
0:01:00
Binary Search Algorithm - Simply Explained
0:09:22
#69 Python Tutorial for Beginners | Binary Search Using Python
0:09:27
Linear & Binary Search Algorithms
Комментарии