Algorithms: Binary Search
Summary
TLDRIn this educational video, Gayle Laakmann McDowell, author of 'Cracking the Coding Interview,' introduces binary search, an efficient algorithm for finding an item in a sorted array. She uses a classroom example with 300 papers to illustrate the concept, highlighting how it quickly narrows down the search space. McDowell explains that binary search operates by repeatedly dividing the array in half, comparing the midpoint with the target, and focusing on the relevant half. The video covers both recursive and iterative implementations, emphasizing the importance of working with sorted data. She challenges viewers to apply binary search to new data types, like strings, after understanding its basic principles.
Takeaways
- 📚 Binary search is an intuitive algorithm used for finding an item in a sorted list by repeatedly dividing the search interval in half.
- 👨🏫 The concept is explained with an analogy of a teacher looking for a student's paper in an alphabetized stack.
- 🔍 The algorithm starts by comparing the target value to the middle element of the array.
- ✅ If the value matches, the search is successful. If not, the search continues in the half where the value could be, based on whether it's less than or greater than the midpoint.
- 📉 The search space is reduced by half with each comparison, making binary search very efficient.
- 🕒 The worst-case time complexity of binary search is O(log n), where 'n' is the number of elements in the array.
- 💻 Binary search can be implemented both recursively and iteratively.
- 🛠️ A common pitfall is integer overflow when calculating the midpoint; this can be avoided by using the formula `(left + right) / 2` instead of `(left + (right - left) / 2)`.
- 🔄 The iterative implementation involves a while loop that continues until the target is found or the search space is exhausted.
- 🔢 Binary search is applicable to any sorted data type, including integers, strings, or other ordered collections.
- 🚀 The script challenges viewers to try implementing binary search on a new data type, such as a string, to reinforce the concept.
Q & A
What is the main concept of binary search as described in the transcript?
-Binary search is an algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one.
How does the teacher-student example illustrate the binary search concept?
-The teacher-student example illustrates binary search by showing how a teacher would efficiently find a student's paper from an alphabetized stack by dividing the stack in half each time and comparing the midpoint with the student's name until the paper is found.
Why is it important for the array to be sorted before performing a binary search?
-The array must be sorted because binary search relies on the order of elements to determine whether to search the left or right half of the array. Without a sorted array, the algorithm would not function correctly.
What is the time complexity of binary search?
-The time complexity of binary search is O(log n), where n is the number of elements in the array. This is because with each comparison, the search space is reduced by half.
How does the recursive implementation of binary search work?
-In the recursive implementation, the binary search function calls itself with adjusted left and right boundaries until it either finds the target value or determines that the value is not in the array.
What is the potential pitfall mentioned in the script regarding the recursive implementation?
-The potential pitfall is integer overflow when calculating the midpoint by adding left and right together. To avoid this, the midpoint can be calculated as (left + (right - left) / 2) instead.
How is the iterative implementation of binary search different from the recursive one?
-The iterative implementation uses a while loop to repeatedly adjust the left and right boundaries without the need for recursive function calls, making it more memory efficient.
What is the condition to exit the while loop in the iterative binary search?
-The while loop in the iterative binary search exits when the left boundary is greater than the right, indicating that the target value is not in the array or the search space has been exhausted.
Can binary search be applied to data types other than integers?
-Yes, binary search can be applied to other data types such as strings, as long as the data is sorted and comparable.
What is the challenge given to the viewer at the end of the transcript?
-The challenge given to the viewer is to try implementing binary search on a new data type like a string.
Outlines
🔍 Introduction to Binary Search
Gayle Laakmann McDowell introduces the concept of binary search using a relatable scenario of a teacher looking for a student's paper in a large, sorted stack. The process involves repeatedly dividing the search space in half by comparing the midpoint with the target, either narrowing down to the left or right half until the item is found or concluded to be absent. The importance of the array being sorted is emphasized, and the efficiency of binary search is explained through its logarithmic time complexity, which is derived from the repeated halving of the search space.
📚 Binary Search Implementation
The paragraph delves into the implementation of binary search, offering insights into both recursive and iterative approaches. The recursive method is first explained, where the search space is defined by 'left' and 'right' pointers, and the midpoint is calculated to decide the next search direction. An alternative method to avoid integer overflow is mentioned. Transitioning to the iterative approach, the paragraph explains how to convert the recursive logic into a loop, adjusting the 'left' and 'right' pointers accordingly without recursion. The necessity for the data to be sorted before applying binary search is reiterated, and the paragraph concludes with an invitation to apply binary search to different data types, such as strings.
Mindmap
Keywords
💡Binary Search
💡Algorithm
💡Sorted Array
💡Midpoint
💡Recursive
💡Iterative
💡Overflow
💡Logarithmic Time Complexity
💡Search Space
💡Implementation
Highlights
Binary search is an intuitive algorithm demonstrated through the example of a teacher finding a student's paper in an alphabetized stack.
The algorithm works by repeatedly dividing the search space in half until the item is found or the search space is empty.
Binary search requires a sorted array to function, emphasizing the importance of initial order.
The efficiency of binary search is explained through the concept of reducing the search space by half with each comparison.
The number of operations in the worst case is equivalent to the logarithm base 2 of the number of elements (n), making it a log n problem.
Binary search can be implemented both recursively and iteratively, offering flexibility in coding approaches.
A recursive implementation of binary search is demonstrated with a clear step-by-step explanation.
An iterative implementation is shown by converting the recursive method, highlighting the simplicity of the conversion.
The potential pitfall of integer overflow in calculating the midpoint is discussed, with a solution provided to avoid it.
The iterative method is detailed, showing how to adjust the indices without recursion.
Binary search's application to other data types like strings is suggested as an exercise for the viewer.
The necessity for the data to be sorted before applying binary search is reiterated for clarity.
The author encourages viewers to practice binary search on different data types to solidify understanding.
The video concludes with a summary of how binary search is implemented and its requirements.
The importance of understanding binary search for coding interviews is implied through the context of the video.
A practical example is used to introduce the concept of binary search, making it relatable and easy to understand.
Transcripts
Hi, I'm Gayle Laakmann McDowell, author of Cracking the Coding Interview. Today I want
to cover binary search. So binary search is a very intuitive algorithm, and I'm going
to show how intuitive it is by giving an example. You're a teacher and you're
teaching a group of students, a very large class of 300 students. And you have
their papers alphabetized out in front of you, when a student Zach Peters comes up
to get his paper back. You probably wouldn't go through the papers
starting with Alex to Andy to Andrew and then to Bob and Brenda and Brandy and into
Chris and Cristine, and you probably wouldn't do that way. What you would probably
do is open the stack of papers to roughly halfway through the
papers and compare it. Zach Peters? Well you open up halfway through and you
see Michael Matters there and you say okay Zach Peters after that name. And
then you take the second stack of papers and treat it as its own little stack and
you'd again say, ok let me open up to its midpoint. Maybe we see Sarah. Well is
Sarah before or after Zach Peters? And then you just go and repeat this process
over and over and over again until you find Zach's paper or until you find out
Zach can't be in here. And this is the basics of binary search. So in an integer
array that looks like this, you take some element that you're looking for, like 13,
and you compare it to the midpoint, and it has to be a sorted array for this to
work,
it's very important, and you compare it to the midpoint. 13 is less than this midpoint
and so 13, if it's in the array at all, it has to be on the left side. And then you repeat
this process on the left side and say let me look at the midpoint of the left
side. Is 13 before and after that, before or after that, and you just repeat that
process until you either find 13 or you know that 13 can't be in it.
So how fast is this is algorithm? Well let's imagine we start off with n elements so
we have a search space of n elements. In a single comparison, just one, we've cut
our search space down to n over 2. Then with one more comparison we cut it down
to n over 4 and then in half again and half
and half and half again. So how many total operations in the very worst case will
we have to run until we figure out if it contains an element or not?
Well the total number of operations we'll have to do is determined by how many
times can we divide n by 2 until we get down to just one. So this is what log of
n expresses. A log base 2 of n expresses. So if you pause the video you
can study that math for a second and see the relationship between those two
things. But this means that binary search is a log n problem. Let's look now at the
implementation of binary search. To implement binary search we can either
implement it recursively or iteratively. We'll do recursive implementation first.
I'm gonna just copy and paste here some just straightforward code for the
binary search call so this is a initial method that calls off to this
binary search recursive method with the right parameters. So we're going to start
off initially with left being zero and right being the very right point, so these
are inclusive endpoints. So first of all, if things get kind of too big, if the left
winds up bigger than right, then we know we have an error, we can't find it. And we
don't want to return true. Otherwise, we want to pick the midpoint so left dot right divided by 2,
so that's going to be the midpoint. And if we found the element, if array of mid is actually the
element we're looking for, then we should return true. Otherwise if X is on the
left side of mid then go search the left side. And as a pass an array X and left will
stay as is and the right point will move to one next to the mid. Otherwise go
search the right side. So we want to call very similar method but now the left point
moves up to mid +1 and right stays as is.
Ok so that's how the binary search recursive implementation looks. So one
little minor pitfall is that, and some people like to be careful of, is that left plus
right can actually overflow it with java integers so if you'd like to avoid the
integer overflow issue you can actually just do this instead and this will
prevent the overflow. It's kind of up to you but this is one way of doing
it.
Ok so now that we've done the recursive implementation let's turn to the
iterative implementation. So what I'm going to do is I'm going to actually
tweak this recursive implementation, I'm going to copy and paste it into a new function, and I'm going to
tweak it to make iterative. So I'm going to call this iterative and I no longer
need parameters in here. But what I'm gonna do is I'm going to set something to show
you how you can tweak it so I'm going to set left to be that right is going to start off
at the rightmost position in the array. So now I want to iterate, I
want to loop through this as long as left and right are such, in the correct
positions. So change this to a while loop.
Alright. And then if I exit here that I haven't found it
Ok so this looks correct and then here I don't want to actually recurse anymore.
What I want to do is essentially take these values here. So left is gonna stay
as is, and right is going to move to mid- minus 1, I'll comment that out and I'll delete
it shortly, and then here rather than, so left is going to stay or left is going
to become mid plus 1 and right is going to stay as is. So that's how easy it is
to tweak it from recursive to iterative. So that's how we implement binary search.
Remember that it can be implemented recursively or iteratively, and it can
also be applied to other data like strings or something else but it must
always operate on something that's sorted. So now that you've seen the
implementation of binary search
why don't you try to do binary search on a new data type like a string.
Good luck.
Ver Más Videos Relacionados
Perhitungan Manual Algoritma Binary Search
Algorithms: Solve 'Shortest Reach' Using BFS
Codeforces Round 839 Div 3 | Problem D: Absolute Sorting Solution | 500 Likes Target | Newton School
Algorithms Explained for Beginners - How I Wish I Was Taught
Binary Search Trees (BST) Explained in Animated Demo
8 patterns to solve 80% Leetcode problems
5.0 / 5 (0 votes)