Is the algorithm implemented by git bisect optimal?
Here's some intuition for what $X$ and $N$ are doing.  Focus on a particular commit $c$.  Suppose we test $c$ and classify it as either "good" or "bad".  Until we test it, we don't know whether it is good or bad, but we can predict in advance how much smaller the graph will get in each of those two cases.  In particular, $X$ is the number of commits that would be trimmed away if commit $c$ turns out to be good, and $N-X$ is the number of commits that would be trimmed away if commit $c$ turns out to be bad.

Therefore, the value $\min(X,N-X)$ is a lower bound on the number of commits we'll be able to trim away in the next step, no matter how the test turns out.  The idea of the Git algorithm is to maximize of this metric.  In other words, Git picks a threshold $t$ that is as large as possible, and a commit $c$ to test next, such that Git can be sure that it'll be able to trim away at least $t$ commits in the next step.

If we have no information about whether each commit is likely to turn out good or bad, so it's equally likely that it's good or bad, then this looks like a locally optimal choice.  Thus, the Git algorithm is a greedy algorithm.

Is the Git algorithm globally optimal?  That will depend upon the definition of "optimal", and (probably) on the distribution of DAGs one encounters in practice.  Probably there is no simple characterization of the probability distribution on DAGs one encounters in practice, so I'd expect it is probably going to be difficult to find an optimality result for this problem.