Core Concept
This prototype is intended to be a visualization of Binary Search.
Why?
Binary search is an important searching algorithm in computer science. It can be difficult for students to understand the idea of eliminating half of the data being searched with each pass the way that binary search is often taught.
The Pitch
Understand the fundamentals of binary search by splitting a 3D cube of colors until the whole cube is the color you want. Use expansive gestures to split the cube along one of three axes and then keep only the half that has the color you’re looking for.
The Experience
This prototype came out quite close to the original pitch. From the center of a lattice of colors, players search for a target color by repeatedly splitting the cube in half and eliminating one section until the entire cube is the target color.
Key Interactions:
- Gesture to split the cube in half along the x, y, or z axis.
- Select the half that contains the target color. The chosen half will expand around you as the other half disappears.
- Repeat this process until the entire cube is the target color.
Key Lessons:
- Binary search is accomplished by repeatedly splitting a sorted set of data in half and only keeping the half that contains the target. (The cube is split in half, one half is selected and the other half disappears.)
- This is repeated until the data being searched contains only the target. (Eventually the cube should be all the same color.)
Step by Step Walkthrough Guide
Demo Video
Team Goals
- Create an immersive visualization of the binary search algorithm.
- Take advantage of working in virtual reality to have players use expansive gestures that feel like magic.
Lessons Learned
Usability:
- It helps players to be able to refer to a small image of the entire cube, as they can’t otherwise see the entire cube at once.
- The gestures to split the cube can be a bit touchy and difficult for the sensor to interpret when the player is facing away from the sensors.
- Players often forget to look up and behind them.
Teaching:
- This does not strictly correspond to a binary search, as the number of nodes do not reduce with each split. However, most players are still able to explain the process of splitting the cube and only keeping half, regardless of whether or not they are familiar with binary search.
- This experience feels a bit like a game, and many players have said that this is the first virtual reality experience they’ve tried where they really wanted to be able to play at home.
- Despite being an abstract illustration of an abstract concept, this prototype gets the concept across quite well.
Role in a Lesson
This experience would be an excellent way of introducing binary search if it were played at or near the beginning of a lesson and followed up with code-based practice and explanation. It could also be used as reinforcement of a lesson if students played it after learning the material.
- The cube represents the entire solution domain.
- Splitting the cube is the central action of binary search.
- The target color is the search target.
If this experience were used as an introduction to the concept, then a teacher could follow it up with code like this, which is a simple pseudo-code representation of what happens in the experience:
/* Binary search in search domain
Pre-condition : the domain is sorted, which mains it maintains monotonicity.
The following sample shows search in a monotonically increasing domain*/
int BinarySearch(int left_bound, int right_bound, type_t target,
type_t search_domain[]){
//Stop condition for the search
if(left_bound == right_bound){
if(search_domain[right_bound] == target)
//target found
return right_bound;
else
//element is not in the domain
return -1;
}//compute the middle value of domain
int middle = (left_bound + right_bound) / 2;//if target is less than middle, search in left half
//else search in right half
if( target < search_domain[middle] )
return BinarySearch(left_bound, middle, target, search_domain);
else
return BinarySearch(middle,right_bound, target, search_domain);
}
Ideas for Future Development
Interface and Usability
- Design a version that accounts for color-blindness.
- Add a way for players to see the path of splits they took to get to their solution.
- Implement a numeric way for players to check how close they are to their goal.
- Add another way for players to compare the two halves of a split to see which contains their target.
- Keep the colored smoke visible at all times, or make it easier to get.
Additional Elements
- Create visuals that give the sense of the searchable space reducing with each split, rather than re-growing around the player.
- Could potentially use this design or a similar one to illustrate other search algorithms, or some simple sorting algorithms.
Teacher Reactions
The teachers we showed this experience to were quite excited about it. Even though most of them were not familiar with binary search, they felt that they had a grasp of the concept after playing and therefore felt that they could definitely use this as an effective teaching tool if they were to teach binary search. One group of teachers pointed out that this sort of experience could be a good addition to a maker space, where students would be able to practice with it on their own time. Another teacher pointed out that this prototype does a good job of teaching the importance of thinking something through before beginning to act, because it is necessary to plan each step before you take it and keep your goal in mind the whole time.
Student Reactions
Students were generally quite excited about this experience. They loved being in the virtual environment and were generally able to pick up the interaction fairly quickly even if it took them a little while to get really comfortable with it. Most students that we showed this prototype to were able to explain the steps they were taking to reach their goal even with no exposure to binary search.
Thoughts From the Team
Miriam – I think this is actually my favorite of the prototypes we built this semester. It’s a fun and beautiful environment to be in, and it’s turned out to be a pretty fun virtual reality game, aside from any teaching potential. My favorite part is being able to ask people to describe the steps they were taking in the game and then say “congratulations, you’ve just described binary search.”
Jiawen – When I think about this, I started from something can’t be made on PC and then went to binary search. In my opinion, it really is a successful prototype, but it seems more about an aesthetic VR experience. Now we need to balance between teaching well and being a great experience. If we could figure out one way that work for these two things it would be wonderful.
Joe – I think this is one of the best prototypes we have done this semester, basically, it not only teaches the basic concept of binary search but also extends it from one dimension to three dimension, which is a good teaching material not only for the beginner but also for someone who already know binary search. However, the drawback of this prototype is players are always in the center of the cube even right after you cut and pick, which gives player an illusion of not changing the range he/she is searching in.
Nick – Color cube is an exemplar for Binary Search. However, there are still several minor tweaks that can possibly strengthen the prototype. Specifically, the regrowing of the half into the cube after splitting does not match exactly to the reduced scope when using binary search algorithm. Instead, it confuses the player. Also, the control of splitting dimension of the circle is hard. Besides these two problems, color cube is an awesome experience and represents binary search very well.
Luna- For this one I really like the fact that it can help test the Graphics card.. Just kidding. It is a good representation of abstract concepts and many playtesters reported that it really help them who has no CS background before visualize the concept. However, it gets opposite feedback from really focused programmers, because some of the representation is not always aligned with traditional binary search that is used in arrays, as it never shrink the search domain.
Click Here to Get the Code and Try it Out for Yourself
Further Reading
To learn more about this prototype and its development, check out these blog posts:
