A Brief Introduction to 2D Binary Searches (C#)
Okay, so I might have made the mistake of attempting a 2D binary search challenge before a standard binary search challenge 😅 Needless to say, I didn’t solve it. But after taking a bit of time to read through some solutions online, watch a couple of videos on them, and familiarise myself with standard binary searches, I feel like I have a grasp on how these work now. Just as we had with binary searches, this is all about narrowing down the searchable area in which a target value is located. If you fancy jumping in at the deep end with this, have a go at this exercise on codingame.com.
In that gamified example, Batman needs to find the location of a bomb (a target location/coordinate) in a building (a grid or 2D array of coordinates). With each iteration of a while loop we’re given a new direction stored in the string “bombDir”. This’ll give us values such as UR (upper-right), L (left), and D (down), to let our algorithm know where the bomb is in relation to batman’s current position. In true binary search fashion, we have Batman jump to the middle position of the viable searchable area again and again until eventually he lands on the bomb. To adjust this searchable area, we can adjust the values of a set of integer values, outlining the minX, maxX, minY, and maxY of the area we’re searching in. A lot of the code essentially parses that bombDir string with each iteration of the loop, changes those values accordingly, and calls the following before changing Batman’s position:
To check out the solution I read through to understand this, please do check out Gaurav Sen’s video and code on GitHub. I made some tweaks to the code to make it work in the latest version of the exercise, as well as some tweaks to make it a little easier for me to understand. I’ll include the code I ended up using below in case you’d like to take a read through that:
Lastly, codingame offers some really nice visualisation of this code in action. I find it pretty mesmerising, and it really does make the efficiency of this sort of algorithm feel all the more impressive 😉
(Appreciate these last couple of articles have been a little code-heavy rather than Unity-oriented, but I’ll be covering some more Unity content shortly 😄)
