My current one takes 1 min 18 s for part 2 (my min attack power for elves to win was about 34) just looping from 3 to 34, no binary chop.
Although for numerous iterations, it has zero cache misses for routing but the iteration still takes a few seconds, so there must be something else taking a bit of time, will profile when at home to find out what.
Refined the cache to be static, and the 'signature' of the board (locations of rock/other units that can't be moved through) part of the cache key.
Probably much faster in C++.
Not particularly pretty:
https://github.com/bjtaylor1/AoC2018/blob/day15part2/Day15/Program.cswhere 'Board' is:
https://github.com/bjtaylor1/AoC2018/blob/day15part2/AoCLib/Board.cs