Exact deterministic Deutsch–Jozsa needs N/2+1 queries

Suppose a deterministic procedure makes at most $N\mathrm{/}2$ queries in the worst case. Run it on the constant-zero function and let $S$ be the set of distinct queried addresses. Write $s=\mathrm{\mid }S\mathrm{\mid }\le N\mathrm{/}2$ and list the complement $C$ in lexicographic order, with $c=\mathrm{\mid }C\mathrm{\mid }$. Concatenating the lexicographic lists of $S$ and $C$ lists every address exactly once: the sets are disjoint and cover the domain. Indexing this concatenated list gives a bijection from $\{0,\dots ,s+c-1\}$ to the $N$-element address set, so $s+c=N$ by [F3]. Thus $c=N-s\ge N\mathrm{/}2$. Choose $T$ to be the first $N\mathrm{/}2$ addresses of $C$ and define $g$ to be $1$ on $T$ and $0$ elsewhere. Then $g$ is balanced and agrees with the constant-zero function on every address in $S$. Inductively, each adaptive query and reply in the two executions is the same, so the final outputs agree despite the different correct answers. Thus no such procedure is exact.

Query any fixed set of $N\mathrm{/}2+1$ distinct addresses. If all replies are equal, the function cannot be balanced because each value occurs only $N\mathrm{/}2$ times in a balanced function, so it is constant. If the replies are not all equal, the function is not constant and is balanced by the promise. This gives an exact procedure using $N\mathrm{/}2+1$ queries; combined with step 1.1 the exact complexity is $N\mathrm{/}2+1$.