Programs / Scala

Binary Search in Scala (Iterative,Recursion,Tail Recursion Approaches)

Binary Search

is a fast & efficient algorithm to search an element in sorted list of elements.
It works on the technique of divide and conquer.
Data structure: Array

Time Complexity:

Worst case: O(log n)
Average case: O(log n)
Best case: O(1)

Space complexity:

O(1)

Let’s see how it can implemented in Scala with different approaches –

Iterative Approach –

Recursion Approach –

Tail Recursion –

Driver Program-

val arr = Array(1, 2, 4, 5, 6, 7)
val target = 7
println(binarySearch_iterative(arr, target) match {
  case -1 => s"$target doesn't exist in ${arr.mkString("[", ",", "]")}"
  case index => s"$target exists at index $index"
})
println(binarySearch_Recursive(arr, target)() match {
case -1 => s"$target doesnt match"
case index => s"$target exists at $index"
})

println(binarySearch_tailRec(arr, target) match {
case -1 => s"$target doesnt match"
case index => s"$target exists at $index"
})

Share This Post

An Ambivert, music lover, enthusiast, artist, designer, coder, gamer, content writer. He is Professional Software Developer with hands-on experience in Spark, Kafka, Scala, Python, Hadoop, Hive, Sqoop, Pig, php, html,css. Know more about him at www.24tutorials.com/sai

Lost Password

Register

Do NOT follow this link or you will be banned from the site!