title: Complexity on sorting or not an integer array
body: <p>I have an array of integers storing some userIDs. I basically want to prevent a user from performing an action twice, so the moment he has done it his userID enters this array.</p>
  
  <p>I wonder whether it is a good idea to sort or not this array. If it is sorted, then you have <code>A={min, ..., max}</code>. Then, if I'm not wrong, checking if an ID is in the array will take <code>log2(|A|)</code> 'steps'. On the other hand, if the array was not sorted then you will need <code>|A|/2</code> (in average) steps.</p>
  
  <p>So sorting seems better to check if an element exists in the array (<code>log(|A|)</code> vs <code>|A|</code>), but what about 'adding' a new value? Calculating the position of where the new userID should be can be done at the same time you're checking, but then you will have to displace all the elements from that position by 1... or at least that's how I'd do it on C, truth is this is going to be an array in a MongoDB document, so perhaps this is handled in some other most-effective way.</p>
  
  <p>Of course if the array is unsorted then adding a new value will just take one step ("pushing" it to the end).</p>
  
  <p>To me, an adding operation (with previous checking) will take:</p>
  
  <ul>
  <li>If sorted: <code>log2(|A|) + |A|/2</code>. The <code>log2</code> part to check and find the place and the <code>|A|/2</code> as an average of the displacements needed.</li>
  <li>If not sorted: <code>|A|/2 + 1</code>. The <code>|A|/2</code> to check and the <code>+1</code> to push the new element.</li>
  </ul>
  
  <p>Given that for adding you'll always first check, then the not sorted version appears to have less steps, but truth is I'm not very confident on the <code>+|A|/2</code> of the sorted version. That's how I would do it in C, but maybe it can work another way...</p>