Complexity of a brute-force search I am currently thinking about the complexity of a brute-force attack on a cipher. Let the key length of the cipher be 64 bit. Then there are $2^{64}$ different keys in the keyspace. If you do a brute-force search, in the middle you will have to search through $2^{63}$ keys for success. So my question is now, what is the complexity of the attack? Is it $2^{64}$ or $2^{63}$? I am not sure about it.
It is exactly $2^{64}$. You need to look for all possible keys for a successful brute-force. One cannot guarantee that the key will be in the half, $2^{63}$, that you are going to search. In, CS there is an adversary argument, that the adversary can always force you to the worst case. Tell him how you the search, he will produce a case that you are not going to find in $2^{63}$ key-space.

Actually, $2^{63}$ is the average case that you will find your keys during the brute-force.

If you have multiple known-plaintext with encrypted different keys then with a multi-target attack you can find some keys faster. The expected cost of finding a key from $t$ target is $2^{64}/t$.