Egbert Lin's Blog

“Life is not a race, but a journey to be savoured each step of the way” by Brian Dyson

Data Structures - Linear Search Algorithm diagram

Posted on Edited on In Disqus:

Basic programming - Linear Search

Question:

Given an array arr[] of n elements, write a function to search a given element x in arr[].

Example:

Input: arr[] = {10, 20, 80, 30, 60, 50, 100, 110, 130, 170}
    x = 110;
Output: 6
Explanation: Element x is presented at index 6

Input: arr[] = {10, 20, 80, 30, 60, 50, 100, 110, 130, 170}
   x = 175;
Output: -1
Explanation: Element x is not presented in arr[].

Source code:

Version 1

Idea
It is a very simple approach to find the target.

Go through each element which is equal to the target (Start from the index 0 of array). If the target doesn't exist in arry, return -1.
However, it is rarely used practically because other search algorithms are more efficient.

Time complexity: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>

using namespace std;

int linearSearch(vector<int> arr, int target){
    for(int i = 0; i < arr.size(); i++){
        if(arr[i] == target) return i;
    }
    return -1;
};

int main()
{
    vector<int> arr{10, 20, 80, 30, 60, 50, 100, 110, 130, 170};
    int x = 110;
    
    int res = linearSearch(arr, x);
    (res == -1)? cout <<"The value isn't exist in array": cout << "The value's index is " << res;

    return 0;
}