title: MS-Access database searching algorithm in O(n)?
body: <p><strong>The Problem</strong></p>
  
  <p>Given a database of 10,000 items, I would like to go about doing the following:</p>
  
  <ol>
  <li>search by any of the columns</li>
  <li>match results by a variable number of letters at the beginning of the result</li>
  <li>print out duplicate results</li>
  <li>the rest of the information for that entry is appended to the search</li>
  </ol>
  
  <p>Consider the table in ms-access (omitting the primary key)</p>
  
  <pre><code>Header1|Header2|Header3
   apple   rotten  green
   apple   fresh   yellow
   pear    fresh   blue
   orange  rotten  pink
  </code></pre>
  
  <p>Given the following search by <em>Header1</em>; apple, pear</p>
  
  <p>I would receive the result:</p>
  
  <pre><code> apple, rotten, green
   apple, fresh, yellow
   pear, fresh, blue
  </code></pre>
  
  <p>Similarly, given the search by <em>Header1</em>; pear, orange, pear</p>
  
  <p>I would receive the result:</p>
  
  <pre><code> pear, fresh, blue
   orange, rotten, pink
   pear, fresh, blue
  </code></pre>
  
  <p><strong>What I'm doing</strong></p>
  
  <p>My approach is to store the header you are searching for and an array containing the elements that you searched for. I retrieve the WHOLE database (it's large so this wouldn't be the preferred method) and order it by the header chosen, and also sort the input that the user gave me (both lists in ascending order).</p>
  
  <p>By using simple comparisons (strComp = 0, -1, 1) I increment counter variables for the respective list. This, however, does not account for the cases where the user inputs a duplicate AND the table has a duplicate result. It only accounts for one or the other of those cases.</p>
  
  <p>My solution to that issue would be to "roll" up and down when we find a result to check for nearby results as well, but that seems horrible, nor does it account for fuzzy string matching.</p>
  
  <p>Any recommendations? The solution should somehow stay O(n) if possible given that the user input can (and will) be > 100,000</p>