Linear Search

Linear search, also known as sequential search, is a simple search algorithm that searches for an element in a list by checking each element in sequence until the target element is found or the end of the list is reached.

A linear search is a simple way to find something in a list. It's like looking for a book on a long shelf. Here's how you can think about it:

Starting at the Beginning: You start at one end of the shelf and look at each book in turn. In a linear search, you start at the first element of a list (or array) and check if it's the one you're looking for.
Checking Each Item: Just like checking each book on the shelf, in a linear search, you check each element in the list one by one. You look at the first item: if it's not the one you're looking for, you move to the next item, and so on.
Finding What You're Looking For: If you come across the book you were looking for on the shelf, you stop searching. Similarly, in a linear search, if you find the element you're looking for in the list, you stop the search.
Reaching the End: If you get to the end of the shelf and haven’t found the book, you know it’s not there. In a linear search, if you reach the end of the list without finding the element, you conclude that the element isn’t in the list.
Simple but Sometimes Slow: Linear search is simple and straightforward, but it can be slow if the list is long, just like it can take a long time to find a book if the shelf is very long. It’s not the most efficient way to search, especially for large lists, but it's easy to understand and implement.

In summary, a linear search is like looking for an item by going through a list one element at a time, from the beginning to the end, until you find what you're looking for or reach the end of the list.

In C++, there are several ways to implement the linear search algorithm:

For Loop

int linearSearch(int arr[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) {
            return i; // element found at index i
        }
    }
    return -1; // element not found
}

While Loop

int linearSearch(int arr[], int n, int x) {
    int i = 0;
    while (i < n && arr[i] != x) {
        i++;
    }
    if (i == n) {
        return -1; // element not found
    } else {
        return i; // element found at index i
    }
}

Note that all of these algorithms have a time complexity of O(n), where n is the size of the array. This means that the time taken to search for an element increases linearly with the size of the array. For large arrays, more efficient search algorithms like binary search or hash tables may be more appropriate.

Example

// This is the main file for the LinearSearch program
#include <iostream>

// Use the standard namespace, so we don't have to qualify identifiers with std:: prefix
using namespace std;

// Function prototype for LinearSearch
int LinearSearch(int[], int, int);

// Entry point of the program
int main() {

   // Initialize an array of numbers to be searched
   int numbers[] = { 2, 4, 7, 10, 11, 32, 45, 87 };

   // Calculate the size of the array
   int numbersSize = sizeof(numbers) / sizeof(numbers[0]);

   // Output the numbers in the array
   cout << "NUMBERS: [" << numbers[0];
   for (int i = 1; i < numbersSize; i++) {
      cout << ", " << numbers[i];
   }
   cout << "]" << endl;

   // Prompt the user to enter an integer to search for
   cout << "Enter an integer value: ";
   int key = 0;

   // Take user input and store it in the variable 'key'
   cin >> key;

   // Perform a linear search to find the key in the array
   int keyIndex = LinearSearch(numbers, numbersSize, key);

   // If the key was not found, print a message indicating it
   if (keyIndex == -1) {
      cout << key << " was not found." << endl;
   }
   // Otherwise, print a message indicating the index where the key was found
   else {
      cout << "Found " << key << " at index ";
      cout << keyIndex << "." << endl;
   }
}

// Function Definitions

// LinearSearch function
// It performs a linear search in the array to find the key
int LinearSearch(int numbers[], int numbersSize, int key)
{
    // Loop through each element in the array
    for (int i = 0; i < numbersSize; i++) {

        // If the current element is the key
        if (numbers[i] == key) {

            // return the index at which the key was found
            return i;
        }
    }

    // If the key was not found in the array, return -1
    return -1;
}

The main function in this program initializes an array of numbers and prompts the user to enter a key to search for. It then uses the LinearSearch function to find the key in the array. If the key is found, it prints a message indicating the index of the key. If not, it prints a message indicating that the key was not found.