Login | Register   
Twitter
RSS Feed
Download our iPhone app
TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK
Browse DevX
Sign up for e-mail newsletters from DevX


Tip of the Day
Language: C
Expertise: Intermediate
Nov 4, 2003

Algorithms: A Linear Search

This is a very straightforward loop comparing every element in the array with the key. As soon as an equal value is found, it returns. If the loop finishes without finding a match, the search failed and -1 is returned.

For small arrays, a linear search is a good solution because it's so straightforward. In an array of a million elements, a linear search will take, on average, 500,000 comparisons to find the key. For a much faster search, take a look at binary search. Example:


int linearSearch(int a[], int first, int last, int key) {
   // function:
   //   Searches a[first]..a[last] for key.
   // returns: index of the matching element if it finds key,
   //         otherwise  -1.
   // parameters:
   //   a           in  array of (possibly unsorted) values.
   //   first, last in  lower and upper subscript bounds
   //   key         in  value to search for.
   // returns:
   //   index of key, or -1 if key is not in the array.

   for (int i=first; i<=last; i++) {
       if (key == a[i]) {
          return i;
       }
   }
   return -1;    // failed to find key
}
Wael Salman
 
Comment and Contribute

 

 

 

 

 


(Maximum characters: 1200). You have 1200 characters left.

 

 

Sitemap