Linear Search | DSA in C++ - Software Development PDF Download

Introduction

In the world of data structures and algorithms, the linear search algorithm is one of the simplest and most fundamental searching techniques. It is used to find a specific element in a given list or array by sequentially checking each element until a match is found. In this article, we will explore the concept of linear search, its implementation in C++, and provide examples and sample problems to help you understand it better.

How does Linear Search work?

The linear search algorithm works by iterating through each element of the array and comparing it with the target element we are searching for. If a match is found, the index of the element is returned. If the entire array is traversed and no match is found, a special value (e.g., -1) can be returned to indicate the element is not present.

Pseudocode for Linear Search

Here is the pseudocode for the linear search algorithm:

• Set the starting index of the array to 0.
• Iterate through each element of the array:
  • a. Check if the current element matches the target element.
  • b. If there is a match, return the index.
• If the entire array is traversed and no match is found, return a special value (e.g., -1) to indicate the element is not present.

Implementing Linear Search in C++

Now, let's see how we can implement the linear search algorithm in C++.

#include<iostream>

using namespace std;

int linearSearch(int arr[], int size, int target) {

    for(int i = 0; i < size; i++) {

        if(arr[i] == target)

            return i;

    }

    return -1;

}

int main() {

    int arr[] = {5, 10, 15, 20, 25};

    int size = sizeof(arr) / sizeof(arr[0]);

    int target = 15;

    int index = linearSearch(arr, size, target);

    if(index == -1)

        cout << "Element not found in the array";

    else

        cout << "Element found at index " << index;

    return 0;

}

Explanation of the code:

• The 'linearSearch' function takes an array 'arr', its size 'size', and the target element 'target' as parameters.
• It iterates through each element of the array using a 'for' loop.
• Inside the loop, it compares each element with the target element using the condition 'if(arr[i] == target)'.
• If a match is found, it returns the index 'i'.
• If the entire array is traversed and no match is found, it returns -1 to indicate that the element is not present.
• In the 'main' function, we declare an array 'arr' and initialize it with some values.
• We calculate the size of the array using 'sizeof(arr) / sizeof(arr[0])'.
• We define the target element 'target' that we want to search.
• We call the 'linearSearch' function with the array, its size, and the target element as arguments and store the result in the 'index' variable.
• Finally, we check the value of 'index' and print the appropriate message based on whether the element was found or not.

Sample Problems

Here are some sample problems you can solve using the linear search algorithm:
Problem 1: Given an array of integers, find the first occurrence of a specific element and return its index. If the element is not present, return -1.

int firstOccurrence(int arr[], int size, int target) {

    for(int i = 0; i < size; i++) {

        if(arr[i] == target)

            return i;

    }

    return -1;

}

Problem 2: Given an array of strings, find the count of a specific string in the array.

int countOccurrences(string arr[], int size, string target) {

    int count = 0;

    for(int i = 0; i < size; i++) {

        if(arr[i] == target)

            count++;

    }

    return count;

}

Conclusion

The linear search algorithm is a simple yet powerful technique to find an element in an array or list. It is particularly useful when the array is not sorted or when the array size is small. In this article, we discussed the concept of linear search, provided an implementation in C++, explained the code, and presented sample problems to enhance your understanding. Practice implementing and solving linear search problems to strengthen your grasp of this fundamental searching algorithm.