Algorithms: Binary Search

Summary

In 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

00:00

🔍 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.

05:07

📚 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.

Keywords

💡Binary Search

Binary search is an efficient 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. In the video, the author uses the analogy of a teacher looking for a student's paper in a sorted stack to illustrate how binary search operates. The concept is central to the video's theme of explaining search algorithms.

💡Algorithm

An algorithm is a set of rules or steps used to solve a problem or perform a computation. In the context of the video, the binary search algorithm is the focus, as it is a method for efficiently locating a specific value within a sorted array. The video aims to demystify how algorithms work, using binary search as an example.

💡Sorted Array

A sorted array is an array where elements are arranged in a specific order, typically ascending or descending. For binary search to function correctly, the array must be sorted because it relies on the order of elements to determine which half of the array to search next. The video emphasizes that binary search is only applicable to sorted arrays.

💡Midpoint

The midpoint in binary search refers to the middle element of the current segment of the array being searched. It is used as a reference point to decide whether to continue the search in the left or right half of the array. The video script describes how the midpoint is calculated and used to guide the search process.

💡Recursive

A recursive implementation of an algorithm involves a function calling itself to solve smaller instances of the same problem. In the video, the author first explains binary search using a recursive approach, where the function calls itself with adjusted parameters to search the left or right half of the array.

💡Iterative

An iterative approach to an algorithm involves using loops to repeat a sequence of operations until a condition is met. The video transitions from a recursive to an iterative implementation of binary search, showing how the process can be achieved without function calls, but rather through the use of loops.

💡Overflow

Overflow in programming occurs when a calculation exceeds the maximum limit that a data type can hold. The video mentions the potential for integer overflow when calculating the midpoint by adding the left and right indices and then dividing by two. It suggests an alternative calculation to prevent this issue.

💡Logarithmic Time Complexity

The time complexity of an algorithm describes the amount of time it takes to run as a function of the size of the input. The video explains that binary search has a logarithmic time complexity, denoted as O(log n), because the search space is halved with each step, making it very efficient for large datasets.

💡Search Space

The search space in the context of binary search refers to the portion of the array that is still being considered for the search. The video script describes how the search space is reduced with each comparison, which is a key feature of the binary search algorithm's efficiency.

💡Implementation

Implementation in programming refers to the process of writing code that realizes an algorithm's logic. The video provides both recursive and iterative implementations of binary search, demonstrating how the abstract concept of the algorithm can be translated into practical code.

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.