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

By submitting your information, you agree that devx.com may send you DevX offers via email, phone and text message, as well as email offers about other products and services that DevX believes may be of interest to you. DevX will process your information in accordance with the Quinstreet Privacy Policy.


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

WEBINAR:

On-Demand

Application Security Testing: An Integral Part of DevOps


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
×
We have made updates to our Privacy Policy to reflect the implementation of the General Data Protection Regulation.
Thanks for your registration, follow us on our social networks to keep up-to-date