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.

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.

## 0 comments:

## Post a Comment