Binary search in Scala
Your code can be much improved by adding a few data structures:

case class Point(x: Int, y: Int)
case class Interval(min: Int, max: Int)
case class Dimensions(horizontal: Interval, vertical: Interval)
case class Direction(relX: Int, relY: Int)


Further you should start to introduce functions everywhere you have a comment now, for instance:

def updateSearchSpace(space: Dimensions, pos: Position, dir: Direction): Dimensions


Since this is a function that receives Dimensions and returns Dimensions as well, it is an ideal candidate to make it a method of the Dimensions class.

In order to simplify the method it is helpful to add a convenience method to Interval first:

case class Interval(min: Int, max: Int) {
  def shrink(newBound: Int, dir: Int) = Interval(
    min = if (dir == 1) newBound else min,
    max = if (dir == -1) newBound else max
  )
}


This allows you to shrink Dimensions pretty elegantly.

case class Dimensions(horizontal: Interval, vertical: Interval) {
  def shrink(pos: Position, dir: Direction) = Dimensions(
    horizontal.shrink(pos.x, dir.relX),
    vertical.shrink(pos.y, dir.relY)
  )    
}


Your new data structures also give you much nicer signatures for your methods in general. 

def loop(x: Int, y: Int, minX: Int, minY: Int, maxX: Int, maxY: Int): Nothing 


becomes

def loop(pos: Position, searchSpace: Dimensions): Nothing


Your function findNewRelativePositionOnAxis(...) looks like it wants to be a member of Interval. I'll leave this one for you as an exercise ;-)