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;
}