Linear Search

Published on 17 October 2019 (Updated: 29 October 2024)

Welcome to the Linear Search page! Here, you'll find a description of the project as well as a list of sample programs written in various languages.

This article was written by:

Jeremy Grifski
Ron Zuckerman

Description

Linear search is quite intuitive, it is basically searching an element in an array by traversing the array from the beginning to the end and comparing each item in the array with the key. If a particular array entry matches with the key the position is recorded and the loop is stopped. The algorithm for this is:

Define a flag (set it's value to 0) for checking if key is present in array or notation.
Iterate through every element in array.
In each iteration compare the key and the current element.
If they match set the flag to 1, position to the current iteration and break from the loop.
If entire loop is traversed and the element is not found the value of flag will be 0 and user can notified that key is not in array.

Performance

The performance of searching algorithms is generally defined in "Big O notation". If you are not familiar with such notations, please refer to the relevant article by Rob Bell or the Wikipedia entry listed in further readings below.

Cases	Big O Notatation
Best case	O(1)
Average case	O(n)
Worst case	O(n)

Linear search is not efficient for large arrays, but for relatively smaller arrays it works fine.

Example: key=3, array=[1, 2, 3, 4, 5]

Iteration 1
array[i] = array[0] = 1
key = 3
key != array[i]

Iteration 2
array[i] = array1 = 2
key = 3
key != array[i]

Iteration 3
array[i] = array2 = 3
key = 3
key = array[i]
break
flag = 1
pos = 2

Requirements

Write a sample program that takes a list of numbers (e.g. "1, 2, 3, 4, 5") and a key (e.g. "3").

linear-search.lang "1, 4, 2, 9" "3"

In addition, there should be some error handling for situations where the user doesn't supply correct input.

Testing

Every project in the Sample Programs repo should be tested. In this section, we specify the set of tests specific to Linear Search. In order to keep things simple, we split up the testing as follows:

Linear Search Valid Tests
Linear Search Invalid Tests

Linear Search Valid Tests

Description	List Input	Target Integer Input	Output
Sample Input First True	"1, 3, 5, 7"	"1"	"true"
Sample Input Last True	"1, 3, 5, 7"	"7"	"true"
Sample Input Middle True	"1, 3, 5, 7"	"5"	"true"
Sample Input One True	"5"	"5"	"true"
Sample Input One False	"5"	"7"	"false"
Sample Input Many False	"1, 3, 5, 6"	"7"	"false"

Linear Search Invalid Tests

Description	List Input	Target Integer Input
No Input
Missing Input: Target	"1, 2, 3, 4"
Missing Input: List	""	"5"

All of these tests should output the following:

Usage: please provide a list of integers ("1, 4, 5, 11, 12") and the integer to find ("11")

Articles

There are 14 articles: