binary search


See On Github

Data

Source Code

object binary_search {

  def search[T: Ordering](values: Array[T], target: T): Int = {
    val ord = Ordering[T]
    import ord._

    if (values.size < 1) {
      return -1
    }

    val mid = values.size / 2
    val midValue = values(mid)

    if (midValue > target) {
      return search(values.slice(0, mid), target)
    } else if (midValue < target) {
      val p = search(values.slice(mid + 1, values.size), target)
      if (p < 0) return -1 else return mid + 1 + p
    }
    mid
  }

}
import org.scalatest.{ Matchers, FlatSpec }
import binary_search._

class binary_search_test extends FlatSpec with Matchers {
  val values = Array(1, 3, 5, 9, 17)
  val expectedPosition = 3
  val target = 9

  "Binary Search" should "find a value and return the position" in {
    val pos = search(values, target)
    pos shouldBe expectedPosition
  }

  it should "return -1 if nothing was found" in {
    val pos = search(values, 4)
    pos shouldBe -1
  }
}