title: Parallel Binary Search
body: <p>I'm just starting to learn about parallel programming, and I'm looking at binary search.</p>
  
  <p>This can't really be optimized by throwing more processors at it right? I know it's supposedly dividing and conquering, but you're really "decreasing and conquering" (from <a href="http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm#Parallelism">Wikipedia</a>).</p>
  
  <p>Or could you possibly parallelize the comparisons? (if <code>X</code> is less than <code>array[mid]</code>, search from <code>low</code> to <code>mid - 1</code>; else if <code>X</code> is greater than <code>array[mid]</code> search from <code>mid + 1</code> to <code>high</code>, else return <code>mid</code>, the index of <code>X</code>)</p>
  
  <p>Or how about you give half of the array to one processor to do binary search on, and the other half to another? Wouldn't that be wasteful though? Because it's decreasing and conquering rather than simply dividing and conquering? Thoughts? </p>