A lost boat, a radar and how to implement a binary search in Javascript

You are part of a rescue operation for a lost boat in the sea.

You have a radar capable of telling you if a boat is in a specific region.

Your goal is to save the crew by coding a function that will return the location of the boat

This was a coding interview question that I was asked when I was searching for my first programming job. We'll have a look at how we can solve it and we'll learn how to implement a binary search algorithm in JavaScript along the way.

Interviewer tips

The task is clear but the interviewer shared a couple more details about the problem:

For simplification purposes, consider the sea is a rectangle grid divided in square cells.

Given inputs: dimensions (width and height) of the sea.

Expected output: location (cell coordinates) of the boat.

Assumptions

We'll consider that the radar takes an area as input which is modelled as a rectangle consisting on a point (top-left one) and its dimensions (width and height). The radar will return true if the boat is present in the area and false if not.

type Area = {
  x: number;
  y: number;
  width: number;
  height: number;
}

type UseRadar = (area: Area) => boolean

First solution: brute force

The first solution that might come to your mind is "let's use the radar on each cell of the sea until we find the boat". We can implement this by using 2 nested for loops that iterate over each axis and stop as soon as the radar finds the boat. The code could look like this:

const getBoatCoordinates = () => {
    for(let x = 0; x < WIDTH; x++) {
      for(let y = 0; y < HEIGHT; y++) {
        if(useRadar({ x, y, width: 1, height: 1 })) return { x, y };
      }
    }
}

This is a valid solution that will return the position of the boat, however, it is not a very efficient one. Imagine that you're checking an area of 100 (width = 10 and height = 10) and that the radar takes 1 minute to return an answer. We would spend 50 minutes on average checking for the boat ( 0.5 * width * height * radarTime ) which is definitely time enough for our boat to sink with all the crew on it. But don't despair, what if I tell you that we can improve the algorithm so that the time spent looking for the boat will be 7 minutes?

Second solution: binary search

Here's is where binary search comes into action. For those of you that are unfamiliar with what binary search is, you can think of it as an iterative algorithm where the search population is divided in half and one of the portions is discarded.

For example, if you wanted to look for a word in a dictionary using this algorithm you would go to the middle page of the dictionary, check on which side your word is and discard the other. Now you would have half a dictionary to look for your word and you could repeat the same operation: divide in two, check where your word is and discard the other portion. You'd keep doing this until you reached your word.

The main advantage of this algorithm is that it decreases significantly the amount of lookups you have to execute as you keep discarding half of the population on each iteration.

Coming back to our boat, we can use the same approach and start splitting our sea in half and check one of the regions with the radar. If the radar returns true we can discard the other region and if it returns false we discard the one we checked. We can keep doing this until we have an area that contains one cell. The boat must be here.

Let's try to implement the algorithm:

const getBoatCoordinatesInArea = (area) => {
  // Area is divided in 2
  const [area1, area2] = divideArea(area);

  // Checks if boat is in first area
  if (useRadar(area1)) {
    return getBoatCoordinatesInArea(area1);
  } else {
    return getBoatCoordinatesInArea(area2);
  }
};

The important bit of this function is what's coming after the if statement, if the boat is in area1 we call the same function with that portion of the sea, if not, then the boat must be in area2 and we call the same function with that chunk.

We are still missing the exit condition in the function, which is the one that will make it stop iterating. We said that we want to exit once the area contains only one cell so let's add it to the code.

const getBoatCoordinatesInArea = (area) => {
  // Exit condition
  if (area.width === 1 && area.height === 1) {
    return { x: area.x, y: area.y };
  }

  // Area is divided in 2
  const [area1, area2] = divideArea(area);

  // Checks if boat is in first area
  if (useRadar(area1)) {
    return getBoatCoordinatesInArea(area1);
  } else {
    return getBoatCoordinatesInArea(area2);
  }
};

Finally, we need an entry point to the function:

const getBoatCoordinates = () => {
    return getBoatCoordinatesInArea({
        x: 0,
        y: 0,
        width: WIDTH,
        height: HEIGHT
  });
}

Here we're just calling the function that we created in the previous step with the entire grid to kickstart the binary search algorithm.

Let's have a look at the number of times we use the radar with this new approach. We need to know the number of times we divide the area in half until we get a single cell. Since we are dividing the grid by 2 on each iteration, we can use the logarithm to the base 2 to get the number: log2(width * height). Now, with our initial inputs we would need the radar 6.64 times but since we cannot use it half a time (you use it or you don't) we need to round the number to the next integer which results in 7 times. This translates into a waiting time of 7 minutes, which gives us enough time to send a rescue boat and save the crew! Hurray!

Comparing both algorithms

We can compare these results with the ones obtained by the brute force algorithm:

Dimensions	Brute force	Binary search
`width = 100` `height = 100`	50 minutes	7 minutes
`width = 200` `height = 200`	200 minutes	9 minutes
Increase %	300%	~30%

We can see that the binary search algorithm is not only better in absolute terms (7 mins vs. 50 mins) but also if the input area grows to twice the height and twice the width the time grows only 30% instead of 300%.

Conclusion

We achieved our goal and the crew is saved! Hopefully, the interviewer liked our solution and the job is ours!

Post a comment if you can think of other algorithms that will save the crew in less time and feel free to reach out if you have any questions!

Bonus: the divideArea function

We didn't implement the divideArea in the code earlier so let's have a look at it here. Since we can divide an area in two axis, we can take 2 different approaches to implement this function. The first one is dividing the area initially on one axis until you reach its limit, for example, you divide vertically until width becomes 1, and then you start dividing on the other axis. The second one is swapping the axis on each iteration, which is a bit more complex since you need to keep track of the divided axis.

Check the first approach here:

const divideAreaVertically = ({ x, y, width, height }: Area): [Area, Area] => {
  const halfWidth = Math.floor(width / 2);
  const leftArea: Area = { x, y, width: halfWidth, height };
  const rightArea: Area = {
    x: x + halfWidth,
    y,
    width: width - halfWidth,
    height,
  };

  return [leftArea, rightArea];
};

const divideAreaHorizontally  = ({ x, y, width, height }: Area): [Area, Area] => {
  const halfHeight = Math.floor(height / 2);
  const bottomArea: Area = { x, y, width, height: halfHeight };
  const topArea: Area = {
    x,
    y: y + halfHeight,
    width,
    height: height - halfHeight,
  };

  return [bottomArea, topArea];
};

const divideArea = (area: Area): [Area, Area] => {
  if(area.width > 1) return divideAreaVertically(area);

  return divideAreaHorizontally(area);
}