BASICSEARCHES

When we are looking for a value in an unordered array, our main option is the
linear search. The linear search is a brute-force-style search. The algorithm works
by stepping through each element of the array, starting with the first element, and
checking to see if the value of that element matches the value of what is being
searched for. If it is found, then the algorithm can report that the item exists in
some meaningful fashion, and it can also report where in the array the item is
positioned.
During a linear search the algorithm can find the first occurrence or all occurrences of a value. If duplicates are allowed in the array, then more than one value
can exist. In this chapter we’ll discuss finding the first occurrence. If there are times
when you know you need to know how many occurrences there are, or even how
many and where they are, then the searching function of the unordered array class
can be expanded to accommodate those needs. Searching beyond the first occurrence can be a waste of CPU time if there is no need to look for duplicates.

template<class T>
class UnorderedArray
{
public:
virtual int search(T val)
{
assert(m_array != NULL);
for(int i = 0; i < m_numElements; i++)
{
if(m_array[i] == val)
return i;
}
return -1;
}
};
A linear search can become slow for arrays with large numbers of items. On
average, the algorithm requires half the total number of items to find a value. If
there were 100 items in a list, then the average would be 50. Because the linear
search’s performance is based on the number of items in the array, it has a big-O of
O(N). The linear search is the most basic, yet slowest, search because it must check
potentially every item (half on average) before finding a value, assuming the value
even exists in the array. If the value does not exist, the search would have checked
every element in the array and come up with nothing.