title: How can we prove by induction that binary search is correct?
body: <p>I'm having a hard time understanding how induction, coupled with some invariant, can be used to prove the correctness of algorithms.  Namely, how is the invariant found, and when is the inductive hypothesis used- particularly for binary search?  I haven't been able to find an intuitive response yet, so I was hoping someone could shed some light on the topic here.</p>