title: How is it possible to do binary search on a singly-linked list in O(n) time?
body: <p><a href="https://stackoverflow.com/q/19554431/501557">This earlier question</a> talks about doing binary search over a doubly-linked list in O(n) time. The algorithm in that answer work as follows:</p>
  
  <ul>
  <li>Go to the middle of the list to do the first comparison.</li>
  <li>If it's equal to the element we're looking for, we're done.</li>
  <li>If it's bigger than the element we're looking for, walk backwards halfway to the start and repeat.</li>
  <li>If it's smaller than the element we're looking for, walk forwards halfway to the start and repeat.</li>
  </ul>
  
  <p>This works perfectly well for a <em>doubly</em>-linked list because it's possible to move both forwards and backwards, but this algorithm wouldn't work in a singly-linked list.</p>
  
  <p>Is it possible to make binary search work in time O(n) on a singly-linked list rather than a doubly-linked list?</p>