Binary Search (Iterative)

On a sorted array, narrow the [lo, hi] window by halving it each step until arr[mid] equals the target or the window is empty. Demonstrates the "discard half the search space" invariant.

Algorithm

Canonical found run uses target = 11 on arr = [1, 3, 5, 7, 9, 11, 13]; it returns index 5 after two midpoint probes.

Basic Implementation

basic.dart

void main() {
  final arr = <int>[1, 3, 5, 7, 9, 11, 13];
  final target = 11;
  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;
      break;
    }
    if (arr[mid] < target) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }
  print(result);
}

Complexity

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

Implementation notes

Dart: use integer division (~/) for mid. Do not call binarySearch from package:collection; it hides the loop the lesson is teaching, and the goal here is zero pub dependencies.
The replay highlights the [lo, hi] window, mid, and which branch (left half / right half / match) the step takes.

inclusive bounds `lo` and `hi` are both inclusive; the loop runs while `lo <= hi`.

overflow-safe midpoint `mid = lo + (hi - lo) ~/ 2` avoids `(lo + hi)` overflow on large inputs.