Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>A <a href="http://en.wikipedia.org/wiki/Linear_search" rel="noreferrer">linear search</a> looks down a list, one item at a time, without jumping. In complexity terms this is an <code>O(n)</code> search - the time taken to search the list gets bigger at the same rate as the list does.</p> <p>A <a href="http://en.wikipedia.org/wiki/Binary_search" rel="noreferrer">binary search</a> is when you start with the middle of a sorted list, and see whether that's greater than or less than the value you're looking for, which determines whether the value is in the first or second half of the list. Jump to the half way through the sublist, and compare again etc. This is pretty much how humans typically look up a word in a dictionary (although we use better heuristics, obviously - if you're looking for "cat" you don't start off at "M"). In complexity terms this is an <code>O(log n)</code> search - the number of search operations grows more slowly than the list does, because you're halving the "search space" with each operation.</p> <p>As an example, suppose you were looking for U in an A-Z list of letters (index 0-25; we're looking for the value at index 20).</p> <p>A linear search would ask:</p> <blockquote> <p><code>list[0] == 'U'</code>? No.<br/> <code>list[1] == 'U'</code>? No.<br/> <code>list[2] == 'U'</code>? No.<br/> <code>list[3] == 'U'</code>? No.<br/> <code>list[4] == 'U'</code>? No.<br/> <code>list[5] == 'U'</code>? No.<br/> ... <code>list[20] == 'U'</code>? Yes. Finished.</p> </blockquote> <p>The binary search would ask:</p> <blockquote> <p>Compare <code>list[12]</code> ('M') with 'U': Smaller, look further on. (Range=13-25)<br/> Compare <code>list[19]</code> ('T') with 'U': Smaller, look further on. (Range=20-25)<br/> Compare <code>list[22]</code> ('W') with 'U': Bigger, look earlier. (Range=20-21)<br/> Compare <code>list[20]</code> ('U') with 'U': Found it! Finished.<br/> </p> </blockquote> <p>Comparing the two:</p> <ul> <li>Binary search requires the input data to be sorted; linear search doesn't</li> <li>Binary search requires an <em>ordering</em> comparison; linear search only requires equality comparisons</li> <li>Binary search has complexity O(log n); linear search has complexity O(n) as discussed earlier</li> <li>Binary search requires random access to the data; linear search only requires sequential access (this can be very important - it means a linear search can <em>stream</em> data of arbitrary size)</li> </ul>
    singulars
    1. This table or related slice is empty.
    1. POWhat is the difference between Linear search and Binary search?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USJon Skeet
    1. USJon Skeet
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. CO+1, although I don't particularly like your dictionary analogy. A better analogy would be the "guess my number between 1 and 100 game" with responses of "you got it", "too high", or "too low".
      singulars
      1. PO
      1. USAdam Rosenfield
    2. COThe dictionary analogy seems fine to me, though it's a better match for interpolation search.
      singulars
      1. PO
      1. USNick Johnson
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload