Learn C++ Programming Language

# 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