This course is the fourth course in the specialization about learning how to develop video games using the C# programming language and the Unity game engine on Windows or Mac. Why use C# and Unity instead of some other language and game engine? Well, C# is a really good language for learning how to program and then programming professionally. Also, the Unity game engine is very popular with indie game developers; Unity games were downloaded 16,000,000,000 times in 2016! Finally, C# is one of the programming languages you can use in the Unity environment. This course assumes you have the prerequisite knowledge from the previous three courses in the specialization. You should make sure you have that knowledge, either by taking those previous courses or from personal experience, before tackling this course. The required prerequisite knowledge is listed in the "Who this class is for" section below. Throughout this course you'll build on your foundational C# and Unity knowledge by developing more robust games with better object-oriented designs using various data structures and design patterns. Data structures and design patterns are both general programming and software architecture topics that span all software, not just games. Although we'll discuss these ideas in the game domain, they also apply if you're writing a web app in ASP.NET, building a tool using WinForms, or any other software you decide to build. Module 1: Explore a Dynamic Array data structure and learn the basics of algorithm analysis Module 2: Learn about and use the common Linked List and Graph data structures Module 3: Learn about and use several additional data structures: Stacks, Queues, and Trees Module 4: Learn why design patterns are so useful and discover a number of design patterns useful in game development Module 5: Complete final peer review “Unity” is a trademark or registered trademark of Unity Technologies or its affiliates in the U.S. and elsewhere. This course is an independent work and is not sponsored by, authorized by, or affiliated with Unity Technologies or its affiliates
Recursive Binary Search
Loading...
来自 University of Colorado System 的课程
Data Structures and Design Patterns for Game Developers
30 个评分
University of Colorado System
30 个评分
课程 4（共 5 门，Specialization C# Programming for Unity Game Development）
从本节课中
Stacks, Queues, and Trees
与讲师见面
Dr. Tim "Dr. T" ChamillardAssociate Professor
Computer Science
In this lecture, we'll look at another problem that we can use recursion to solve.
Specifically, we'll see how we can do binary search using recursion.
We will again use Visual Studio so we can use
the debugger to look at how recursive binary search works.
So we'll walk through one of these,
where we have an array.
Of one, three, five, 12, 17, 21,
33, 42, 42 and 42.
And we are going to do a binary search of this array.
So we are going to pass in the number we're looking for, which is three.
We're going to pass in the array we're going to search,
we'll pass in the lower bound and will pass in the upper bound.
So we start with a lower bound of zero and an upper bound of the array length minus one.
We start by saying,
we need to search the entire array.
Let's go look at the binary search method to see how it works.
So as I said, we pass in a search value in the array,
and a lower bound and an upper bound.
And we are going to recurse until one of two things happen.
So we have two base cases in this particular case.
One of those base cases is that there is nothing else to look at,
and that is the case when lower bound is greater than upper bound,
then there is nothing else for us to look at.
So we return negative one because we didn't
find the value we were looking for in the array.
We also might have found the search value when we look at the middle location,
and so if we've found the value,
we return it's location.
And here's where the recursion comes in.
If in fact, the middle value is greater than search value,
then we know that the value we're looking for is on the left.
So we make a recursive call to the method.
We're still looking for search value,
and we're still looking for it in the search array.
We leave the lower bound the same,
but we set the upper bound to middle location minus one.
So now we're looking at a chunk of the array to the left of middle location.
Similarly, if the middle value is less than search value,
then we are going to search for the value in the array.
But this time we're going to look to the right of middle location.
So our lower bound gets moved up to middle location plus one,
and our upper bounds stays the same.
So let's use the debugger to watch what happens.
I'll set a break point here in the binary search method,
and we will start debugging with F5.
So we are looking for the value three,
the call stack shows our first call on the binary search method,
our lower bound is zero and our upper bound
is nine because we have 10 elements in the array.
I will have F10 a few times so we're calculating the middle location,
and down here on the left you can see that the middle location is four at this point.
And we F10 one more time,
and middle value is 17.
So we know 17 is greater than the three we're looking for,
we are going to keep searching.
I'll F5, so you can see over here in
the call stack or in our recursive call on the binary search method,
at this point lower bound is zero and upper bound is three.
I'll F10 and I'll F10 one more time,
and a middle location is one and middle value is three.
So we've actually just found with one recursive call,
two calls to the binary search method,
but when recursive call to the binary search method where we changed upper bound,
so we were shrinking the conceptual size of
the array that we were searching for the element each time we called the method.
And so this is our first base case,
I'll F10 to show you that we in fact,
are going to return middle location because
we found three which is what we're looking for.
I'm going to F5 again,
and I will tell you that this time we are searching for
the value 43 which is not in the array.
We start with our lower bound of zero and our upper bound of nine.
And I will F5 and you'll see in the call stack this is our first recursive call.
And because 43 was greater than 17,
we are now going to change our lower bound to five and our upper bound to nine.
Let's see what that middle value we're comparing to is.
It's 42, and 43 is greater than 42 so I'm going to F5 again.
Here you can see in the call stack we're now in
our second recursive call to binary search.
Lower bound is eight,
upper bound is nine.. We're going to find 42 again,
so I'll F5 again.
Here you can see lower bound and upper bound are both nine,
and we're in our third recursive call to the binary search method.
I'll F5 one more time.
There's our last recursive call,
lower bound is 10,
and upper bound is nine.
So I will F10 to show you that we're returning negative one
here because we hit the other base case for the recursion,
where there was nothing else to look at,
and we didn't find the value we were looking for in the array.
To recap. In this lecture,
we saw how we can do a binary search using recursion.
