Well I only count 32 notes, but I'm on my phone so maybe I don't get to see the whole thing.

That said, A is the last note I see, and it seems there is a count of ~11,000 for that note. So to me that's ~11,000 instructions to waste before a new interupt. That's tons of time if I understand your chart correctly. In any event, I like to get things done fast. My suggestion is a hybrid search. Maybe check the middle, decide higher or lower, then do a linear search from there.

Now back to the numbers: If each test took 25 instructions and you have 50 tests: that's 1250 instructions. Approx 10% of the time between interupts. So still no prob.