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

Basic Implementation

Basic.java
Replay: real traced execution (multi-file project)
public class Basic {
    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 4, 4, 7, 9};
        int target = 4;
        int lo = 0;
        int hi = arr.length - 1;
        int result = -1;
        while (lo <= hi) {
            int 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;
            }
        }
        System.out.println(result);
    }
}

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

    1public class Basic {2    public static void main(String[] args) {
    values this step[1, 2, 4, 4, 4, 7, 9]arr4target-1result

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

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

  3. lo ← 2, mid ← 1

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

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

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

  5. stdout ← 2

    18    }19    System.out.println(result);20}
    values this step2stdout2result

Complexity

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

Implementation notes

  • Java stores the sorted input in a primitive int[], so arr[mid] reads copy primitive values from checked array slots while lo, hi, mid, and result remain local int variables.
  • The midpoint uses the overflow-safe form lo + (hi - lo) / 2 inside the while (lo <= hi) bounds guard. Window updates keep future indexed reads inside 0 through arr.length - 1.
  • On a match, the code assigns result = mid and then moves hi = mid - 1, continuing left to find the first occurrence among duplicate 4 values. Lower values move lo = mid + 1; higher values move hi = mid - 1.
  • The replay-visible states show result changing from -1 to 3, then to 2, before lo > hi ends the loop. Aside from the initial array, the search uses primitive locals and creates no ongoing JVM GC pressure.