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 C# DSA version keeps the same data and final output as every other DSA book in this wave.

Basic Implementation

basic.cs
Replay: real traced execution (multi-file project)
using System;

class Program {
	static int Search(int[] arr, int target, int lo, int hi) {
		if (lo > hi) return -1;
		int mid = lo + (hi - lo) / 2;
		if (arr[mid] == target) return mid;
		if (arr[mid] < target) return Search(arr, target, mid + 1, hi);
		return Search(arr, target, lo, mid - 1);
	}

	static void Main() {
		int[] arr = new int[] { 1, 3, 5, 7, 9, 11, 13 };
		int target = 11;
		Console.WriteLine(Search(arr, target, 0, arr.Length - 1));
	}
}

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

    1using System;
    values this step0lo6hi11target

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

    5if (lo > hi) return -1;6int mid = lo + (hi - lo) / 2;7if (arr[mid] == target) return mid;
    values this step3mid7arr[mid](4, 6)next call0lo6hi

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

    5if (lo > hi) return -1;6int mid = lo + (hi - lo) / 2;7if (arr[mid] == target) return mid;
    values this step5mid11arr[mid]5result4lo6hi

  4. stdout ← 5

    1using System;
    values this step5stdout5result

Complexity

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

Implementation notes

  • Keep the explicit recursive method instead of calling BCL search helpers so the replay can show the branch chosen at each stack frame.
  • int mid = lo + (hi - lo) / 2 keeps midpoint arithmetic overflow-safe, and each arr[mid] read from the managed reference int[] is bounds-checked by the CLR.
  • Each recursive call carries a narrower lo/hi window on the normal C# call stack; the lo > hi return keeps the empty-window base case explicit in the implementation.