Introduction to Search Algorithms

Introduction to Search Algorithms

A search algorithm is a method of locating a specific item of information in a larger collection of data. This section discusses two algorithms for searching the contents of an array.

The Linear Search

This is a very simple algorithm.
It uses a loop to sequentially step through an array, starting with the first element.It compares each element with the value being searched for and stops when that value is found or the end of the array is reached.

Program 8.1
// This program demonstrates the searchList function, which
// performs a linear search on an integer array.

#include

// Function prototype
int searchList(int [], int, int);

const int arrSize = 5;

void main(void)
{
int tests[arrSize] = {87, 75, 98, 100, 82};
int results;
results = searchList(tests, arrSize, 100);
if (results == -1)
cout << « You did not earn 100 points on any test\n »;
else
{
cout << « You earned 100 points on test « ;
cout << (results + 1) << endl;
}
}
// The searchList function performs a linear search on an
// integer array. The array list, which has a maximum of numElems
// elements, is searched for the number stored in value. If the
// number is found, its array subscript is returned. Otherwise,
// -1 is returned indicating the value was not in the array.

int searchList(int list[], int numElems, int value)
{
int index = 0; // Used as a subscript to search array
int position = -1; // To record position of search value
bool found = false; // Flag to indicate if the value was found
while (index < numElelments && !found)
{
if (list[count] == value)
{
found = true;
position = index;
}
index++;
}
return position;
}

Program Output
You earned 100 points on test 4

Efficiency of the Linear Search
The advantage is its simplicity.
It is easy to understand
Easy to implement
Does not require the array to be in order
The disadvantage is its inefficiency
If there are 20,000 items in the array and what you are looking for is in the 19,999th element, you need to search through the entire list.

Binary Search

The binary search is much more efficient than the linear search.It requires the list to be in order.The algorithm starts searching with the middle element.If the item is less than the middle element, it starts over searching the first half of the list.If the item is greater than the middle element, the search starts over starting with the middle element in the second half of the list. It then continues halving the list until the item is found.