Searching

Binary Search (Recursive)

Use the same binary-search window as the iterative lesson, but pass lo and hi through recursive calls.

Algorithm

Basic Implementation

basic.scala 
object Main {
	def search(arr: Array[Int], target: Int, lo: Int, hi: Int): Int = {
		if (lo > hi) return -1
		val mid = lo + (hi - lo) / 2
		if (arr(mid) == target) return mid
		if (arr(mid) < target) return search(arr, target, mid + 1, hi)
		search(arr, target, lo, mid - 1)
	}

	def main(args: Array[String]): Unit = {
		val arr = Array(1, 3, 5, 7, 9, 11, 13)
		val target = 11
		println(search(arr, target, 0, arr.length - 1))
	}
}

Complexity

  • Time: O(log n)
  • Space: O(log n) call stack

Implementation notes

  • search(arr: Array[Int], target: Int, lo: Int, hi: Int): Int takes the Scala Array[Int], target, and current bounds as parameters on each call.
  • The miss base case is if (lo > hi) return -1, so -1 is the not-found sentinel.
  • val mid = lo + (hi - lo) / 2 computes the current index with Int integer division before reading arr(mid).
  • A match returns mid immediately. If arr(mid) < target, the function recurses with mid + 1, hi; otherwise it recurses with lo, mid - 1.
  • The top-level input is val arr = Array(1, 3, 5, 7, 9, 11, 13) and val target = 11.
  • The trace starts with search(lo=0, hi=6), computes mid = 3, sees arr(mid) = 7, and recurses right to (4, 6).
  • The next call computes mid = 5, sees arr(mid) = 11, returns 5, and println(search(...)) prints the exact output 5.
execution replay The checked-in replay follows the language-neutral state table for `search-binary-recursive`.
cross-language comparison This Scala DSA version keeps the same data and final output as every other DSA book in this wave.