Aaron Gadberry

Help – v. helped, help·ing, helps

Was this site helpful?
My Amazon.com Wishlist

Searching: Linear Search

24th January 2006 - By Paradochs

Information

  • Order: O(n)
  • Best Case: O(1)
  • Average: O(n/2)

Description (from wikipedia)

In computer science, linear search is a search algorithm, also known as sequential search, that is suitable for searching a set of data for a particular value.

It operates by checking every element of a list until a match is found. Linear search runs in O(N). If the data are distributed randomly, on average N/2 comparisons will be needed. The best case is that the value is equal to the first element tested, in which case only 1 comparison is needed. The worst case is that the value is not in the list, in which case N comparisons are needed.

C++ Files and Code Listings

This code has a few built in functions to time the sort and count the number of comparisons.
This code was written and compiled successfully in Visual Studio .NET.

LinearSearch.h
/* Travis Gadberry Patrick Hesser Chris Ladewig LinearSearch.h 21Mar05 */ #ifndef LINEARSEARCH_H #define LINEARSEARCH_H #include <vector> #include <time.h> using namespace std; class LinearSearch { public: LinearSearch(); LinearSearch(int *, int); LinearSearch(vector<int>); ~LinearSearch(); bool search(int); double getSearchTime(); int getSearchIncrements(); private: int * A; int n; int increments; double time; }; #endif
LinearSearch.cpp
/* Travis Gadberry Patrick Hesser Chris Ladewig LinearSearch.cpp 21Mar05 */ #include "LinearSearch.h" using namespace std; LinearSearch:: LinearSearch() { n = 1; A = new int[n]; A[0] = 0; increments = 0; time = 0; } LinearSearch:: LinearSearch(int * array, int N) { n = N; A = new int[n]; for(int i = 0; i < n; i++) A[i] = array[i]; increments = 0; time = 0; } LinearSearch:: LinearSearch(vector<int> V) { n = V.size(); A = new int[n]; for(int i=0; i<n; i++) A[i] = V.at(i); increments = 0; time = 0; } LinearSearch:: ~LinearSearch() { delete(A); } bool LinearSearch:: search(int key) { time_t t1, t2; t1 = clock(); bool found = false; for(int i=0; i<n && !found; i++) if(increments++, key==A[i]) found = true; t2 = clock(); time = (t2 - t1)/CLOCKS_PER_SEC; return found; } int LinearSearch:: getSearchIncrements() { return increments; } double LinearSearch:: getSearchTime() { return time; }

Leave a Reply

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>