in the switch example code, the default is to let the user know that the user did not enter the correct choice.
The linear search is a very simple algorithm. Sometimes called a sequential search , 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 either the value is found or
the end of the array is encountered. If the value being searched for is not in the array, the
algorithm will unsuccessfully search to the end of the array. For example:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
|
int searchList(const 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 < numElems && !found)
{
if (list[index] == value) // If the value is found
{
found = true; // Set the flag
position = index; // Record the value's subscript
}
index++; // Go to the next element
}
return position; // Return the position, or −1
}
|
The binary search is a clever algorithm that is much more efficient than the linear search.
Its only requirement is that the values in the array be sorted in order. Instead of testing the
array’s first element, this algorithm starts with the element in the middle. If that element happens
to contain the desired value, then the search is over.
For example:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
|
int binarySearch(const int array[], int numElems, int value)
{
int first = 0, // First array element
last = numElems − 1, // Last array element
middle, // Midpoint of search
position = −1; // Position of search value
bool found = false; // Flag
while (!found && first <= last)
{
middle = (first + last) / 2; // Calculate midpoint
if (array[middle] == value) // If value is found at mid
{
found = true;
position = middle;
}
else if (array[middle] > value) // If value is in lower half
last = middle − 1;
else
first = middle + 1; // If value is in upper half
}
return position;
}
|