Ok let me explain, imagine #125 as number 750, if we subtract 500 (2^124, half of 2^125 or in our example 2^125 = 1000) if we subtract 500 from 750 we'd have 250, now all we have to do is to figure out what number is closest to our 250 (which we don't know it's exact value) and try to subtract that guessed number from our 1/3 of #125 puzzle, and the rest would be easy.
Guessing the right number is very hard. And you can always guess it wrong, subtract 800 from 750, and you will get -50. Then, assuming that your N is 1000000, you will try to break 999950, instead of trying to break 750. Also, as far as I know, people already start from some offset, so they are not trying to scan keys outside of that 500 to 1000 range, instead they just pick for example 550 to 560 range, and try to scan only that, and that alone takes a lot of time.
Though if you could explain how to figure out which key is greater or smaller than the other, that would be awesome!
You cannot figure it out, based only on a single public key. It is always relative to the base point. For example, if you have (basePoint,yourPoint) pair, you could have "yourPointPrivKey" as some even number, for example 250. But it is only even in a relation between this particular base point! So, only "basePoint*250=yourPoint" gives you "250" as an even number. However, you could use (basePoint*2,yourPoint) pair instead, and then your private key would be odd, and equal to 125. See? Your private key is not universally assigned to your public key alone, it is always relative to your base point. And for that reason, if there would be any algorithm that could give you a private key, based on some public key, it would take at least a pair of public keys as arguments.
For the same reason, there is no such thing as "which key is greater or smaller than the other". ECDSA is working like a clock, you can give me some two public keys, and then I could calculate "(firstPubKey+secondPubKey)/2", and then say that the distance between my point, and any of your two points, is identical.