I am exactly mid-way in my PhD in computer science. Is this the right time to start looking for a post doc?
Around your last year.
So much of this comes from networking though, so it is important to be meeting people at conferences long before you are about to graduate.
In the US, many postdoc positions are filled quite late (often after faculty offers have gone out, so mid to late Spring, maybe even early Summer) but you should start talking to potential postdoc advisors maybe a year before your graduation to put a bug in their ear.