# Find It in log n

*Task 4 of 5 · [Stream Compaction](https://gpu.rocks/learn/stream-compaction-0aed2e43.md) · GPU.js Learn*

The search you just wrote reads all 64 flags per thread. Across 64 threads that
is 4,096 reads to move 30-odd values — worse than the CPU's single pass. It works, and it
is the right shape, but it throws away the one thing that makes the array searchable:
`offsets` **never decreases**.

Add the flag back to it and you get the **running count** —
`offsets[i] + flags[i]`, how many survived up to and including `i`.
It is non-decreasing too, and it steps up by exactly one at each survivor. So the element
for output cell `j` is the *first index whose running count exceeds
`j`*, and a sorted array is something you can binary-search: seven
halvings settle 64 elements instead of 64 reads.

This is a *lower bound* search — keep a window `[lo, hi)`, look at
its midpoint, and throw away the half that cannot contain the answer. When the window is
empty, `lo` is the index you wanted.

## Figures

- **the running count only ever goes up, so you can halve your way to it**

## Goal

**Goal:** replace the linear search with a binary search over the
running count, and return the sample it lands on.

## Requirements

- Keep a window `lo` … `hi`, starting at `0` and `this.constants.n`
- Halve it `this.constants.steps` times, testing `offsets[mid] + flags[mid]` against `this.thread.x`
- Return `samples[lo]` — clamped to the last index, because `lo` can finish at `n`

## Hint 1 — what you are searching for

For output cell `j` you want the smallest index whose running count
is **greater than** `j`. Greater than, not equal to: the
running count reaches `j + 1` exactly at the survivor destined for slot
`j`.

## Hint 2 — one halving

If the midpoint's running count already exceeds `this.thread.x`,
the answer is at `mid` or to its left, so `hi = mid`. Otherwise
the answer is strictly to the right, so `lo = mid + 1`. Nothing else
changes.

## Hint 3 — the whole body

```js
let lo = 0;
let hi = this.constants.n;
for (let s = 0; s < this.constants.steps; s++) {
  if (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (offsets[mid] + flags[mid] > this.thread.x) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }
}
return samples[Math.min(lo, this.constants.n - 1)];
```

The `if (lo < hi)` guard matters: the window can empty before the seventh
halving, and a midpoint of an empty window is an out-of-bounds read.

## Same idea elsewhere

Device-side binary search is a first-class primitive —
`thrust::lower_bound`, CUB's `DeviceSelect` internals, and the
merge-path partitioning that load-balances GPU merges and sparse-matrix products all lean
on it. Production compactors often go one step further and build a *scatter-address
table* instead: one pass writes each output slot's source index, a second gathers
through it, trading a buffer for the search entirely. Same inversion, one more array.

## Starter code

```js
// Same gather, log n reads: binary-search the running count.
const gpu = new GPU({ mode });

const compact = gpu.createKernel(function (samples, flags, offsets) {
  let lo = 0;
  let hi = this.constants.n;
  for (let s = 0; s < this.constants.steps; s++) {
    if (lo < hi) {
      const mid = Math.floor((lo + hi) / 2);
      // TODO: compare the running count at mid — offsets[mid] + flags[mid] —
      // against this.thread.x, and throw away the half that cannot hold the
      // answer. One of the two branches has to move lo past mid.
      hi = mid;
    }
  }
  return samples[Math.min(lo, this.constants.n - 1)];
}, {
  output: [64],
  constants: { n: 64, steps: 7 },
});

const packed = await compact(samples, flags, offsets);
console.log('samples:', samples.slice(0, 12).join(', '));
console.log('packed: ', Array.from(packed).slice(0, 12).join(', '));
```

---

Interactive version: https://gpu.rocks/learn/stream-compaction-0aed2e43/4

[Previous task](https://gpu.rocks/learn/stream-compaction-0aed2e43/3.md) · [Next task](https://gpu.rocks/learn/stream-compaction-0aed2e43/5.md)