Problem

Given an array of n elements and a element ‘x’, write a program to search an element ‘x’ in the array.

Examples

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// Example 1
Input [] = {20, 30, 40, 10, 5, 2, 60, 73}, int x = 10
Output: Index 3

// Example 2
Input [] = {20, 30, 40, 10, 5, 2, 60, 73}, int x = 60
Output: Index 6

// Example 3
Input [] = {20, 30, 40, 10, 5, 2, 60, 73}, int x = 9
Output: No Found

Solution

Algorithm

  • Begin with the leftmost element of the array.
  • Check if the element matches ( x ).
  • If it matches, return its position.
  • If not, move to the next element and repeat the process.
  • If all elements are checked and none match ( x ), then ( x ) is not in the array.

Here is the dry run below:

Code

Java

1
2
3
4
5
6
7
8

public int linearSearch(int[] input, int x) {
    for (int i = 0; i < input.length; i++) {
        if (x == input[i]) {
            return i;
        }
    }
    return -;1
}

Python

1
2
3
4
5
6
7
8
9

def linearSearch(my_list, item):
    found = False
    position = 0
    while position < len(my_list) and not found:
        if my_list[position] == item:
            return position;
        position = position + 1
    return -1

Time Complexity Analysis

Time Complexity

O(n) where n is number of elements in array

Space Complexity

O(1) as we dont use any extra space.