Depends a lot on the problem, for medium probably between 15-30 min for most. I have interviewed at FAANG companies for software roles and done the whole on-site leet coding gauntlet. Did about an hour a night for a week total prep. I can solve their problems, what gets me is when I finished early and they ask more academic follow up questions. Like getting backed into a corner and having to admit I have no idea what big-O notation is.

How do you know that scanning an array looking for a number in a sorted array vs. searching for it is slower? Just kind of intuitively? Do you have your own terms for it? I too sometimes get dinged because I use the non academic terms for things...

Can be anywhere from 1 minute to hours, depends on the problem. The whole classification thing is kind of ridiculous, because some hard problems are easy and some mediums are hard.