DS 1 - Solve Problems with Linear Search Algorithm

linear-search-image

In programming, everyone has to learn a very basic linear search algorithm. In this algorithm, we tried to search a given number from a list (array) by checking all the list elements (search linearly).

With linear search, we check all the possible answers and try to find which is correct or not. (Brute force solution)

Problem: Write a program to find the steps required to search a given number from a list(array) of numbers. If you found the number then return the position. Otherwise, return -1.

nums = [1, 5, 3, 6, 7, 18, 13, 17]
target = 6
output = 3

Linear Search Algorithm

General idea is to search through a list in a linear fashion. (Element by element)

Steps:

1. Create a variable position with value 0 (index 0).
2. Check if the number at the index position in nums equals the target number.
3. If it does, return position as the answer.
4. If it’s not, increment the value of the variable position by 1.
5. Repeat the steps from 2 to 4 till the last position.
6. If the target number is not found in the list(array), return -1.

Based on the algorithm, below is the function:

# linear search algorithm
# Time complexity: O(N) | Space complexity: O(1)
def linear_search(nums, target):
    position = 0
    while position < len(nums):
        if nums[position] == target:
            return position
        position += 1
    return -1

The above algorithm’s runtime complexity is O(N) and space complexity is O(1).

Linear search algorithm is very is to write based on specific problems but with large arrays, it is very difficult to perform because of O(N) runtime complexity. Like, if we find two numbers in the given list then runtime complexity will get increased to O(N²).