Search Algorithm in C++ programming
Definition of search algorithm
A search algorithm is a method of locating a specific item in a collection of data. It’s very common for programs not only to store and process data stored in arrays, but to search arrays for specific items.
This tutorial will show you two methods of searching an array: the linear search and the binary search. Each has its advantages and disadvantages.
The linear search
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 search to the end of the array.
The following program is a complete program that uses the searchList function. It searches the five element tests array to find a score of 100.
#include <iostream>
using namespace std;
int searchList(int [], int, int);
const int SIZE = 5;
int main() {
int tests[SIZE] = {87, 75, 98, 100, 82};
int results; // Holds the search results
// Search the array for the value 100
results = searchList(tests, SIZE, 100);
// If searchList returned -1, 100 was not found
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) << ".\n";
}
return 0;
}
int searchList(int list[], int size, int value) {
int index = 0; // Used as a subscript to search array
int position = -1; // Used to record position of search value
bool found = false; // Flag to indicate if the value was found
while (index < size && !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
}
Program Output :
You earned 100 points on test 4
The binary search
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 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.
Otherwise, the value in the middle element is either greater than or less than the value being searched for.
If it is greater than the desired value then the value (if it is in the list) will be found somewhere in the first half of the array. If it is less than the desired value then the value (again, if it is in the list) will be found somewhere in the last half of the array. In either case, half of the array’s elements have been eliminated from further searching.
The following program is a complete program using the binarySearch function. It searches an array of employee ID numbers for a specific value.
#include <iostream>
using namespace std;
int binarySearch(int [], int, int);
const int SIZE = 20;
int main() {
// Create an array of ID numbers sorted in ascending order
int IDnums[SIZE] = {101, 142, 147, 189, 199, 207, 222,
234, 289, 296, 310, 319, 388, 394,
417, 429, 447, 521, 536, 600 };
int empID, // Holds the ID to search for
results; // Holds the search results
cout << "Enter the employee ID you wish to search for: ";
cin >> empID;
results = binarySearch(IDnums, SIZE, empID);
// If binarySearch returned -1, the ID was not found
if (results == -1)
cout << "That number does not exist in the array.\n";
else {
cout << "ID " << empID << " was found in element "
<< results << " of the array.\n";
} return 0;
}
int binarySearch(int array[], int size, int value) {
int first = 0, // First array element
last = size - 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;
}
Program Output :
Enter the employee ID you wish to search for: 199
ID 199 was found in element 4 of the array.
Obviously, the binary search is much more efficient than the linear search. Every time it makes a comparison and fails to find the desired item, it eliminates half of the remaining portion of the array that must be searched.
Ads Right
