Searching

Binary Search (Recursive)

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

Algorithm

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.

Basic Implementation

basic.scala
Replay: real traced execution (multi-file project)
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))
	}
}

  1. lo ← 0, hi ← 6, target ← 11

    1object Main {2	def search(arr: Array[Int], target: Int, lo: Int, hi: Int): Int = {
    values this step0lo6hi11target

  2. mid ← 3, arr[mid] ← 7, next call ← (4, 6)

    3if (lo > hi) return -14val mid = lo + (hi - lo) / 25if (arr(mid) == target) return mid
    values this step3mid7arr[mid](4, 6)next call0lo6hi

  3. mid ← 5, arr[mid] ← 11, result ← 5

    3if (lo > hi) return -14val mid = lo + (hi - lo) / 25if (arr(mid) == target) return mid
    values this step5mid11arr[mid]5result4lo6hi

  4. stdout ← 5

    12	val target = 1113	println(search(arr, target, 0, arr.length - 1))14}
    values this step5stdout5result

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.