Computer scienceProgramming languagesScalaControl flowFunctions

Tail recursion

Theory

Binary search

Report a typo

We need to implement the binarySearch function which must find the index of the target value in a sorted Vector by minimum operations. If the function cannot find the target, it must return None. Finish the implementation via tail recursion.

Sample Input 1: 

1 13 44 55 72 81
55

Sample Output 1: 

Some(3)
Write a program in Scala 3
import scala.annotation.tailrec

@tailrec
def binarySearchTail(numbers: Vector[Int], target: Int, low: Int, high: Int): Option[Int] =
if low > high then None
else
val mid = (low + high) / 2
if numbers(mid) == target then ???
else if numbers(mid) > target then binarySearchTail(numbers, target, low, ???)
else binarySearchTail(numbers, target, ???, high)

def binarySearch(numbers: Vector[Int], target: Int): Option[Int] =
binarySearchTail(numbers, target, 0, numbers.length - 1)
___

Create a free account to access the full topic