Currently if a transaction is reverting, EstimateGas will exhibit worst-case behavior and binary search up to the max gas limit (~40 state-clone + tx executions).
We could consider is whether it's worth it to hone in on the exact gas usage needed, or if something "close enough" is enough. Currently by binary searching until hi == lo + 1, we're wasting a lot of executions to get the exact to-the-gas accuracy, which is unnecessary while most wallets will just add some random number on top to account for network conditions.
Most txs don't need much higher gas limit than their gas used, and most txs don't require near the full block limit of gas. So the selection of where to bisect the range is skewed to favour the low side.
hi == lo + 1, we're wasting a lot of executions to get the exact to-the-gas accuracy, which is unnecessary while most wallets will just add some random number on top to account for network conditions.