Introducing Divide & Conquer

[00:00:02]
>> Bianca: I'm gonna keep going guys. Divide and conquer, are you ready? So, Divide and Conquer is a recursive technique for taking a larger problem, breaking into subproblems and doing work on each of those subproblems to reach some goal, some solution. And let's take a look at some results.

[00:00:24]
So a classic example of a Divide and Conquer algorithm is Binary Search. So, Mario here is looking at a sorted list of numbers. Let's say this is 1, 2, 3, you know 6, 9, 12, there's about 15 or 16 here. Let's say there's 16. And let's say that we're looking for, say that's 10, okay.

[00:00:51]
I'm not counting each one. So we can do, you know, we can go through and look at each one until we get to 10 and that's going to be a linear search. Where we just go and look at each one. However, since it's sorted we can break it in half and just search within one-half.

[00:01:11]
So when we get to the middle, so the first step of Divide and Conquer is we divide. And then once we get into the division step, we need to decide which direction to go. We don't go both directions because that would be against the whole point of the Divide and Conquer, where we only want to evaluate half or a part of our data set.

[00:01:33]
So we're going to go to the middle. We can say, is 10 less than 8 or greater than 8 and we're gonna say it's greater than 8. So we're just gonna throw away, the rest. And we're gonna go to the middle of the greater than side. So we know that everything to the right is going to be greater than, let's say 8.

[00:01:53]
And so we're gonna go into the middle of 8 which, let's say that's like 11 or so. Here and it's gonna say okay, is 10 greater than 11 or less than 11. So it's a less than 11, so we're gonna throw away all of these things. Again it's sorted so we know everything to the right is gonna be greater than 11.

[00:02:11]
And then we hop into the middle of the rest of our data that we're looking at. And in this case, that's the answer. But we may even have to do it again where we say is it greater than or less than until we get to our solution. And the reason that this is an important algorithm is that it takes something that's linear and turns it into logarithmic time.

[00:02:42]
How do we know it's logarithmic time because the work that we have to do is cut in half every single time. So the data set that we're evaluating for our number is decreasing by half each time. And so that's binary search. Again, binary search has to be sorted.

[00:03:02]
You get an interview question and it says, you have an assorted array, you should be thinking hm, binary search, automatically. Or, if they're like, you're searching an array, you can say is that array sorted? If it is, binary search is the way to go. If it's not, there are other searching algorithms.

[00:03:21]
But linear search is a good one, where you just are going to loop through your list and look for that number.