Searching

Binary Search First Occurrence

Find the first copy of a duplicated target by recording matches and continuing to search the left half.

Algorithm

execution replay The checked-in replay follows the language-neutral state table for `search-binary-first`.
cross-language comparison This Dart DSA version keeps the same data and final output as every other DSA book in this wave.

Basic Implementation

basic.dart
Replay: real traced execution (multi-file project)
void main() {
  final arr = [1, 2, 4, 4, 4, 7, 9];
  const target = 4;
  var lo = 0;
  var hi = arr.length - 1;
  var result = -1;
  while (lo <= hi) {
    final mid = lo + (hi - lo) ~/ 2;
    if (arr[mid] == target) {
      result = mid;
      hi = mid - 1;
    } else if (arr[mid] < target) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }
  print(result);
}

  1. arr ← [1, 2, 4, 4, 4, 7, 9], target ← 4, result ← -1

    1void main() {2  final arr = [1, 2, 4, 4, 4, 7, 9];
    values this step[1, 2, 4, 4, 4, 7, 9]arr4target-1result

  2. hi ← 2, mid ← 3, result ← 3

    7while (lo <= hi) {8  final mid = lo + (hi - lo) ~/ 2;9  if (arr[mid] == target) {
    values this step6 → 2hi3mid3result0lo

  3. lo ← 2, mid ← 1

    7while (lo <= hi) {8  final mid = lo + (hi - lo) ~/ 2;9  if (arr[mid] == target) {
    values this step0 → 2lo1mid2hi3result

  4. hi ← 1, result ← 2, mid ← 2

    7while (lo <= hi) {8  final mid = lo + (hi - lo) ~/ 2;9  if (arr[mid] == target) {
    values this step2 → 1hi3 → 2result2mid2lo

  5. stdout ← 2

    17  }18  print(result);19}
    values this step2stdout2result

Complexity

  • Time: O(log n)
  • Space: O(1)

Implementation notes

  • Keep the explicit control flow. Library shortcuts would hide the state changes this lesson is meant to replay.
  • The final output is intentionally small and deterministic for cross-language comparison.