- [Instructor] Searching.
We've seen binary search trees earlier,
and related trees, AVL trees, and splay trees.
And these are designed to make search easy.
And these have big O of log n average case
complexity for search.
Here's a quick table that shows the average case
and the worst case.
If you'll recall,
binary search tree has the worst case
of big O of n when we have that pathological structure
that all branches go in one direction.
So we have essentially a linear chain of nodes.
And AVL tree and splay tree are designed to mitigate
that condition to keep the tree balanced
and keep the performance in the range
of O log n.
Splay tree, of course, is amortized
over a number of operations.
And search can be faster
if we repeatedly access the element at the root.
But in the average case, it's big O of log n.
But now the question arises.
What do we do about searching a linear structure?
Often, we're faced with arrays or vectors,
and we want to find whether a value exists
in an array or where, if a particular value exists
in an array.
So we want to be able to return the index
of a particular value.
And so what do we do in cases like this?
If the array is unsorted,
then brute force is the only approach.
We have to check every element,
and that's big O of n.
So if we wanted to find the value 35 here,
we'd have to search each individual value until we found 35.
What if we wanted to find 42?
We'd have to go all the way to the end.
What if we searched for the value 56
which is not in this array?
We'd have to go all the way to the end
to verify that it is not, in fact, in the list.
So that's why we have a complexity of O of n.
That's if the array is unsorted.
Now, you'll recall when we were justifying sorting,
we were saying, it's great because if you sort once,
then you can find values more quickly ever thereafter.
So here, we have the same values
we had in the previous array, but now they're sorted.
So now how can we make search faster?
If the array's sorted,
then we know if we've gone too far.
Okay. So if we're looking for a 64,
and we do 12, 35, 42, 44, 50, 63, 72.
Oops, we've gotten to a value that's bigger than 64.
And we haven't found 64
so we know we can terminate early.
But that's only a small help.
Doing a linear search is still an order of O of n.
And we can do better.
Can you think how?
If you don't already know the answer,
pause the video here
and puzzle over this for a bit.
Let's say we wanted to find 42.
We'd start by finding the middle of our array.
We could take the maximum index
plus the minimum index and integer divide by two.
In this case here,
eight minus zero divided by two gives us four.
So we look for 42 in the middle here.
We find the value 50.
And we know that if 42 is in this array,
it must be to the left.
So we know it's not an index four
since 42 is less than 50.
And the array is sorted,
so we know it must be to the left of 50
if it's in the array at all.
Now we calculate the middle index
of the subarray on the left.
That's three plus zero divided, integer divided by two.
And that gives us one.
And so we go to index one.
Now the value is 35.
But 42 is greater than 35
so we know that it must lie to the right of 35,
excluding the portion
of the array that we've already ruled out.
So again, we calculate, now, indices three plus two.
Integer divided by two gives us two.
And now we found 42.
Notice that at each step,
we cut the size of our search space in half.
Now this should be setting
off bells and whistles in your heads.
What's the maximum number of steps that this kind of search
will need in order to find a value in a sorted array
or determine that it's not in the array?
Well, it's O of log n.
And this is called binary search.
Here's some pseudo code.
This just outlines what I've already walked you through.
We start with the minimum value at zero.
That's the minimum index in our vector.
We set the maximum to be the length of the vector minus one.
That's the largest index in our vector.
And then we have a while loop.
And we simply keep calculating the middle,
and resetting the maximum or the minimum,
depending on whether our target
is less than the value
that we find at the middle or greater
than the value that we find in the middle.
If neither of these cases holds,
then we must've found the value.
So we return the index.
And then, if we get through this entire while loop
and we don't find the value,
then we can return null or some sentinel value.
In the book, they used negative one.
It's a sentinel value to indicate
that your search has failed.
That's a common approach.
So binary search gives us a way to search
through a sorted array in big O of log n.
Here's another approach it's called interpolation search.
Let's say we wanted to find 38.
We know the minimum value in our array is zero.
And the maximum value is 90.
That's a range of 90.
So where would we expect to find 38 in a range like that?
Well, we take 38 divided by 90.
That will give us .42.
And we multiply that by the maximum index
minus the minimum index, which gives us eight.
That gives us a value of 3.37, and we truncate.
And so we would expect to find 38 at index three.
And in fact, that's exactly where it is.
Now this is a nice example with values more
or less uniformly spread out between the minimum
and the maximum.
Notice that they're spread out more or less evenly.
Not exactly, but pretty close.
So we have values more or less uniformly spread out
between the minimum and the maximum.
And if we have an array like this,
then interpolation search works quite nicely.
Let's look at another example.
Here, the values aren't quite so uniformly distributed.
So we start with the same calculation.
The range of values is still from zero to 90.
And we get that .42 when we take this division.
And we multiply by the range of indices here,
and we get 3.37.
And we truncate to three and we've look
in that position in the array.
And we find that 38 is not there.
So now what do we do?
Well, we can exclude all the values
to the left of that position, including that position.
Since we know 38 is greater than 18,
and we know that we have a sorted list.
Well, the first calculation is the same as before.
Now our calculation doesn't simplify.
We were able to simplify before
because our starting point was zero,
and that simplified our calculation a little bit.
But this isn't too much more complicated.
We calculate the expected position of 38
within the range of values from 21 to 90.
And then we multiply that by our range of indices.
That's from four to eight.
And we add the offset of our starting index.
That's four.
So we have 38 minus 21.
That's the 21 is the first value
in our new subarray divided by 90 minus 21.
That's the complete range of values we have here.
And we get, you see, .28.
And then we take .28 times eight minus four.
That's eight.
Here's the largest index, four is the smallest index.
And we add the offset of the smallest index.
And that gives us a value of 5.11.
And so we truncate and we're gonna look at position five.
And there, we find 38.
That's exactly where we expected to find it.
And that's where it was.
And notice that this took two steps.
Whereas binary search would have taken three.
In the case of binary search,
we'd have started at the middle, 21.
And we would have determined
that it was to the right of 21.
We would have found the middle there
which would have been 66,
and then determined that it would have had to have been
to the left of 66.
And so we would have found it on the third step.
So here again, interpolation search
outperforms binary search.
So what's the downside of interpolation search?
Well, in order to work well,
values must be more or less uniformly distributed.
And as the values deviate
from a uniform distribution,
performance of interpolation search deteriorates.
Here's a kind of a pathological example.
This is kind of like our worst case binary search tree.
It's a pathological example, but it illustrates the point.
So interpolation search won't work well
for an array like this.
Say we want to find seven.
Well, the range of values here is zero, 9,999 minus zero.
And so if we calculate the position
of seven divided by 9,999,
that would lead us to index zero and our search would fail.
So we'll try again.
And we calculate the expected position
of seven in the range from one to 9,999.
And we end up at index one,
and that would fail.
And so we do it again, we'd calculate the expected position
of seven and the range from two to 9,999.
And we'd wind up at index two and so on.
So here, our search would be of order O of n.
Notice we had to scan almost the entire array to find seven.
That's a worst case for interpolation search.
Here's some pseudo code.
And all this does is it outlines the procedure
that I've used before.
Notice that there are some edge cases
that are not considered here.
And you'll find a note to that effect in the book as well.
But this is a simplified version of interpolation search.
We initialize the minimum and the maximum.
We have the while loop.
We calculate the expected position
within the range of values.
We apply that to the difference between the maximum
and the minimum indices that we're searching on,
and add the offset of the minimum.
And then again, just as with a binary search,
we update max or min, depending on
whether the target is less than the value
at the position we calculated,
or whether it's greater than
the value at the position we calculated.
And again, if those are equal,
we found it and we returned the index.
Otherwise, we returned null or some sentinel value.
Again, in your book, they use negative one
as the sentinel value.
So in summary, we have a linear search,
which has an average case of O of n,
and a worst case of O of n.
We don't like that.
So if we have a sorted list, we can do binary search
or interpolation search.
Binary search has average and worst case of O of log n.
Interpolation search has an average case
of O of log log n.
And the calculation of that complexity is outside
the scope of the book and this course.
It's a non-trivial calculation.
But notice that the elements
have to be uniformly distributed
in order to achieve that performance.
And the worst case of interpolation search,
as we've just seen is, O of n.
Now this is gonna motivate our next topic
which is called hashing.
And hashing is a way of finding values in constant time.
We'll see more about that later.
That's all for now.