The Linear Search

The linear search is a very simple algorithm. Also known as the sequential search 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 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.

// This program uses the linear search algorithm
// to search the five-element array tests to find a score of 100.

#include <iostream>

using namespace std;

// Function prototype
int linearSearch(const int[], int, int);

int main() {
    const int SIZE = 5;
    int tests[SIZE] = { 87, 75, 98, 100, 82 };
    int results;

    // Search the array for 100.
    results = linearSearch(tests, SIZE, 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;
    }

    return 0;
}

//***************************************************************
// The linearSearch function performs a linear search on an     *
// integer array. The array arr, which has a maximum of size    *
// 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 linearSearch(const int arr[], int size, 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 < size && !found) {
        if (arr[index] == value) {
            position = index;
            found = true;
        }
        index++;
    }
    return position;
}

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 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. Otherwise, the value in the middle element is either greater than or less than the value being searched for. If it is greater, then the desired value (if it is in the list) will be found somewhere in the first half of the array. If it is less, then the desired value (again, if it is in the list) will be found somewhere in the last half of the array.

If the desired value wasn't found in the middle element, the procedure is repeated for the half of the array that potentially contains the value.

Here is the pseudocode for a function that performs a binary search on a array:

Set first to 0
Set last to the last subscript in the  array
Set found to false
Set position to -1
While found is not true and first is less than or equal to last
    Set middle to the subscript halfway between array[first]
    and array[last]
    If array[middle] equals the desired value
        Set found to true
        Set position to middle
    Else If array[middle] is grater than the desired value
        Set last to middle - 1
    Else
        Set first to middle - 1
    End If
End While
Return position

// This program uses the binary search algorithm
// to search an array of employee ID numbers for a specific value.

#include <iostream>

using namespace std;

// Function prototype
int binarySearch(const int[], int, int);

int main() {
    const int SIZE = 20;
    // Array with employee IDs sorted in ascending order.
    int id_numbers[SIZE] = {101, 142, 147, 189, 199, 207, 222,
                            234, 289, 296, 310, 319, 388, 394,
                            417, 429, 447, 521, 536, 600};
    int results;     // To hold the search results
    int employee_id; // To hold the employee ID

    // Get an employee ID to search for.
    cout << "Please enter the employee ID you wish to search for: ";
    cin >> employee_id;

    // Search for the ID.
    results = binarySearch(id_numbers, SIZE, employee_id);

    if (results == -1)
        cout << "The ID does not exist in the array.\n";
    else {
        cout << "That ID is found at element " << results;
        cout << " in the array.\n";
    }

    return 0;
}

//***************************************************************
// The binarySearch function performs a binary search on an     *
// integer array. array, which has a maximum of size 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 binarySearch(const int array[], int size, int value) {
    int first = 0;       // First array element
    int last = size - 1; // Last array element
    bool found = false;  // Flag
    int position = -1;   // Position of search value
    int middle;          // Midpoint of search

    while (first <= last && !found) {
        // In C++, int divides int equals int. Ex: 5 / 2 = 2.
        middle = (first + last) / 2;
        if (array[middle] == value) {
            found = true;
            position = middle;
        } else if (array[middle] > value) {
            last = middle - 1;
        } else {
            first = middle + 1;
        }
    }
    return position;
}

Output:

Please enter the employee ID you wish to search for: 199
That ID is found at element 4 in the array.

Qingquan-Li / blog

Linear Search and Binary Search (C++) #215

The Linear Search

The Binary Search