Gas estimates, are there cases where the binary search can be skipped?

[ArielElp]

I wanted to bring up gas estimates, in particular gas estimates that happen after the optimistic estimate here:

1. When can transactions fail on the optimistic run due to out of gas? Is it possible for transactions that do not use the GAS opcode?
2. Assuming the transaction is guaranteed to not use the GAS opcode, can g^*, the minimal amount of start gas required to run successfully, be smaller than ~ g+g', where g is the gas consumed when starting to run with infinite gas (first iteration), and g' is the refunded gas in the first iteration.

In essence, my question is whether the binary search can be skipped assuming the GAS opcode does not exist.