Explore
For Enterprise
Join for Free
Log In

浏览
搜索
企业版
登录
免费加入

Recursive Binary Search

Loading...

Data Structures and Design Patterns for Game Developers

科罗拉多大学系统

4.7（38 个评分） | 3.3K 名学生已注册

课程 4（共 5 门，C# Programming for Unity Game Development 专项课程）

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

查看授课大纲

审阅

4.7（38 个评分）

5 stars
32 ratings
4 stars
3 ratings
3 stars
2 ratings
1 star
1 ratings

DC

Jun 29, 2018

Some concepts were really challenging and the course was much more demanding than any other course in the specialization. In any case, it was extremely rewarding to get to the end! Thanks, Dr. T!

ZL

Jul 15, 2018

this course contains well illustrated knowledge of coding with good depth

从本节课中

Stacks, Queues, and Trees

Lesson Introduction1:37

Recursive Binary Search6:17

Tree Implementation11:07

Tree Analysis7:56

Tree Traversal9:02

Minimax Search9:03

Minimax Implementation9:57

教学方

Dr. Tim "Dr. T" Chamillard
Associate Professor

脚本

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.

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

Coursera

关于
管理团队
工作机会
目录
证书
MasterTrack™ 证书
学位
企业版
政府版
面向校园

社区

学生
合作伙伴
开发者
Beta 测试人员
专业译员
博客
技术博客

更多

条款
隐私
帮助
内容访问
媒体
联系我们
目录
附属公司

随时随地学习

关注我们

© 2019 Coursera Inc.保留所有权利。