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"
})