Home / Questions / 343793
Accepted
Carlos
Asked: 2020-04-07 04:34:34 +0800 CST 2020-04-07 04:34:34 +0800 CST

Search for an element in an Array by recursion in Scala

  • 772

Hello everyone, I just started using Scala and I have a problem that I can't get out of, I need to find an element within an array by recursion with an auxiliary function called search, which takes parameters from the left and right ends. The truth is that I am very overwhelmed because the compiler does not give me any error, it just seems that it does not enter the BinaryRec search method when I put it in the println. First of all, thanks for your help, this is what I have so far:

  import scala.io.StdIn._

def busquedaBinariaRec[A](x:A,xs:Array[A])(implicit ord : Ordering[A]): Any ={
  //implementarlos recursivamente sin usar bucles
  import ord._
  buscar(0, xs.length -1)
  def buscar (izq:Int, der:Int):Any = {
    var indice : Option[Int] = None
    var izq = 0
    var der = xs.length -1
    if (indice.isEmpty && izq <= der) {
      val cen = (izq+der)/2
      val y = xs(cen)
      if (x==y) indice=Some(cen)
      else if (x>y)
       izq = cen +1
      else
        der = cen-1
    }
   return indice 
  }

}
  println("¿Cual es el Array?")
val xs = Array[Int](1, 5, 6, 10, 14, 20, 50) //El Array sobre el que queramos realizar la busqueda lo cambiamos aqui
println(xs.mkString("Array(", ", ", ")"))
println("Introduce el elemento que quieras buscar")
val n: Int = readInt()
println(busquedaBinariaRec(n, xs))
}
scala

1 Answers

  1. Best Answer

    A first piece of advice : take advantage of the fabulous system of scala types. Never use the Anyreturn type from a function if you don't want any surprises later.

    The function busquedaBinariaRecwill return the result of the last statement, which is the definition of the function buscar, definition that results in a type Unit, which is what it returns and does not print anything in the println.

    I assume that this is not the expected result, that what you wanted was for the function buscarto call itself, recursively, and return the final result, the index of the element within the Array.

    If you had put the data type that it returns, Option[Int], it would have given you an error at compile time, before executing anything.

    The signature of busquedaBinariaRecshould be:

    def busquedaBinariaRec[A](x:A, xs:Array[A])(implicit ord : Ordering[A]): Option[Int]

    As for the definition of buscar, it would be something like this:

    def buscar (izq: Int, der: Int): Option[Int] = {
  if (izq > der)
    None
  else{
    val cen = (izq + der)/2
    val y = xs(cen)
    if (x == y)
      Some(cen)
    else if (x < y) 
      buscar(izq, cen-1)
    else
      buscar(cen+1, der)
    }
  }

    Second tip : Avoid using variables whenever you can.

    Now we put it all together:

    def busquedaBinariaRec[A](x:A, xs:Array[A])(implicit ord : Ordering[A]): Option[Int] = {
  import ord._

  def buscar(izq: Int, der: Int): Option[Int] = {
    if (izq > der)
      None
    else{
      val cen = (izq + der)/2
      val y = xs(cen)
      if (x == y)
        Some(cen)
      else if (x < y) 
        buscar(izq, cen-1)
      else
        buscar(cen+1, der)
      }
    }

  buscar(0, xs.length-1)
}

    The last statement is the one that executes the recursive function and returns the result.

    It may be clearer with the method compare:

    def busquedaBinariaRec[A](x:A, xs:Array[A])(implicit ord : Ordering[A]): Option[Int] = {
  import ord._

  def buscar(izq: Int, der: Int): Option[Int] = {
    if (izq > der)
      None
    else{
      val cen = (izq + der)/2
      compare(x, xs(cen)) match {
        case 0 => Some(cen)
        case -1 => buscar(izq, cen-1)
        case 1 => buscar(cen+1, der)
      }
    }
  }

  buscar(0, xs.length-1)
}
    • 2