The puzzle is available here.

Binary Search

In this article I am going to talk about what is binary search and how to solve a puzzle related to it on the CodinGame site.

To understand binary search lets first talk about linear search. Linear search is the algorithm when we start off at the beginning of a list and compare our value with every element of that list. While this is effective the problem with it is how much time it takes to find a certain element.

The amount of time an algorithm needs to run is referred to as time complexity denoted with O. The time complexity of the linear search is O(n) where n is the number of inputs to the function.

This means that the time to find a certain element is increase linearly with the amount of elements we have. In other words if it takes us 1s to iterate through a 1 element list (this is much faster in reality, 1s is just for simplicity’s sake) than it will take us 2s with a list with 2 members, 3s with a list of 3 and so on.

This is fine is some cases but as we can see it could get really slow after a certain amount of elements.

The specialty of binary search is that it has a time complexity of O(log n). This means that the amount of time needed increases with each added element how the values increase on a chart with a logarithmic function.

Time complexities of functions:¹

For us to be able to use a binary search there is a prerequisite tho, the array we look at has to be ordered, in other words the 1st element is either the smallest or the largest and it increases or decreases as we move through it.

What binary search does is that we take our ordered list and we set 3 variables, one to the front (or left) on the the middle, and one to the back (or right). Now we can check if the value is equal to the middle (if yes we are done), greater or less than it. For simplicity’s sake our list increases from left to right.

If our value is greater than the middle we can discard anything from the middle down till the left end and we set our left variable to be middle + 1 since we know our element is not in that region. Now we calculate a new middle, check again and if our value is less than the middle we discard the right side by setting our right variable to be equal to middle – 1.

This is how it looks like in C++:²

// C++ program to implement iterative Binary Search
#include <bits/stdc++.h>
using namespace std;

// An iterative binary search function.
int binarySearch(int arr[], int low, int high, int x)
{
    while (low <= high) {
        int mid = low + (high - low) / 2;

        // Check if x is present at mid
        if (arr[mid] == x)
            return mid;

        // If x greater, ignore left half
        if (arr[mid] < x)
            low = mid + 1;

        // If x is smaller, ignore right half
        else
            high = mid - 1;
    }

    // If we reach here, then element was not present
    return -1;
}

// Driver code
int main(void)
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, 0, n - 1, x);
    if(result == -1) cout << "Element is not present in array";
    else cout << "Element is present at index " << result;
    return 0;
}

Lets move on to the puzzle.

Puzzle

In this puzzle we have to set Batman’s position equal to the Joker’s bomb within a certain amount of steps. Since there is a limitation of how many iterations we have before the bomb explodes we cannot use linear search, because it would take too much time, but fortunately for us, we are working with and ordered list here.

There are a few differences we have to account for: we have a 2D list here and we do not know the bombs exact position, however we do know our own position.

The program will give us an input according to where to bomb is compared to us, is it left (L), right (R), up (U) or down (D) from our position.

To account for the 2D list, we just have to check 2 different variables instead of 1. If the bomb is above us (U) we need to decrease our position and if it is below (D) than we have to increase it. Similarly with left and right where with left (L) we decrease and with right (R) we increase our position’s value.

Here we can just use our positions as if we were the middle. In the very first iteration it is not gonna be true but that is alright, after every other round it is.

So what we do is we take the low and high end of the lists, based on the game’s input we set the low or high end to our position ±1, we calculate the middle and move there.

This is how the solution looks like in C++:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/

int main()
{
    int w; // width of the building.
    int h; // height of the building.
    cin >> w >> h; cin.ignore();
    int n; // maximum number of turns before game over.
    cin >> n; cin.ignore();
    int x0; // column
    int y0; // row
    cin >> x0 >> y0; cin.ignore();
    int w_low = 0;
    int w_high = w - 1;
    int h_low = 0;
    int h_high = h - 1;

    // game loop
    while (1) {
        string bomb_dir; // the direction of the bombs from batman's current location (U, UR, R, DR, D, DL, L or UL)
        cin >> bomb_dir; cin.ignore();
        string jump;

        // Write an action using cout. DON'T FORGET THE "<< endl"
        // To debug: cerr << "Debug messages..." << endl;
        if(bomb_dir[0] == 'R' || bomb_dir[1] == 'R'){
            w_low = x0 + 1;
        } else if(bomb_dir[0] == 'L' || bomb_dir[1] == 'L'){
            w_high = x0 - 1;
        }

        if(bomb_dir[0] == 'D' || bomb_dir[1] == 'D'){
            h_low = y0 + 1;
        } else if(bomb_dir[0] == 'U' || bomb_dir[1] == 'U'){
            h_high = y0 - 1;
        }

        x0 = w_low + (w_high - w_low) / 2;
        y0 = h_low + (h_high - h_low) / 2;

        jump = to_string(x0) + ' ' + to_string(y0);

        cerr << "bomb_dir: " << bomb_dir << endl;
        cerr << "w_high: " << w_high << endl;
        cerr << "w_low: " << w_low << endl;
        cerr << "w_mid: " << x0 << endl;
        cerr << "h_high: " << h_high << endl;
        cerr << "h_low: " << h_low << endl;
        cerr << "h_mid: " << y0 << endl;
        // the location of the next window Batman should jump to.
        cout << jump << endl; // order is column than row
    }
}

If you have any questions feel free to ask me in the comments or on Xitter.

Hope to see you here again!

Thanks for reading!
Sincerely,
B4D4M

1. https://www.geeksforgeeks.org/what-is-logarithmic-time-complexity/ ↩︎
2. https://www.geeksforgeeks.org/binary-search/ ↩︎