Linear Search

What is a searching algorithm?

• A searching algorithm is a method to find a specific value or element within a data structure.

What is a linear search?

• The linear search is a standard algorithm used to find elements in an unordered list. The list is searched sequentially from the start to the end one element at a time, comparing each element to the value being searched for
  • If the value is found the algorithm outputs where it was found in the list
  • If the value is not found it outputs a message stating it is not in the list
• An example of using a linear search would be looking for a specific student name in a list or searching for a supermarket item in a shopping list

Performing the linear search

Figure 1: Performing the Linear Search

Time complexity of a linear search

• To determine the algorithm’s execution time as measured by the number of instructions or steps carried out, Big-O notation must be used
• The loop is executed n times, once for each item. There are two instructions within the loop, the if statement and an assignment, hence the Big-O for the loop is O(2n)
• There are three initial statements which are O(1)
• The overall Big-O notation is therefore 2n + 3, which when coefficients are factored out, becomes O(n) as linear time dominates constant time. The constant term and coefficients contribute significantly less as the input size n grows larger
• It is important to remember here that O(n) is the worst case scenario. The best case scenario O(1) would find the item the first time, while the average case would be O(n/2) which when we remove coefficients still becomes O(n)

Space complexity of a linear search

• Linear search has a space complexity of O(1) because it does not require any additional memory that grows with the size of the input
• It only uses a constant amount of extra space, such as a loop counter or a variable to store the target value

Tracing a linear search

• Given the following list [5, 4, 7, 1, 3, 8, 9, 2], a trace table for the linear search is shown below, with target value 3:

Step	Index (i)	Value at Index list[i]	Comparison (Value == 3)	Result
1	0	5	5 == 3	False
2	1	4	4 == 3	False
3	2	7	7 == 3	False
4	3	1	1 == 3	False
5	4	3	3 == 3	True (Found)

Implementing a Linear Search

function linearSearch(list, item)
    index = -1
    i = 0
    found = False
    while i < len(list) and found = False
        if list[i] = item then
            index = i
            found = True
        endif
        i = i + 1
    endwhile
    return index
endfunction

• Initialisation: The function accepts a list of items and the target value. It initializes index to -1 (a standard default indicating the item is not found), i to 0 (the starting position), and a found flag to False.
• Search Criteria: The while loop is designed to continue only as long as the end of the list hasn’t been reached and the item has not yet been located.
• Comparison Logic: During each iteration, the algorithm checks if the current element list[i] matches the target item.
• Found State: If a match is detected, the current position is saved to index and the found flag is set to True, which acts as a signal to terminate the loop immediately.
• Iteration: If the current element does not match, the counter i is incremented by 1 to move the search to the next element in the sequence.
• Return Value: Once the loop finishes, the function returns the index. This will either be the numerical position of the item or -1 if the entire list was searched without success.

def linear_search(list, item):
    index = -1
    for i in range(len(list)):
        if list[i] == item:
            index = i
            break  # Stop the loop early once the item is found
    return index