Research Paper on Linear Search Algorithm

Introduction

The linear search algorithm is a simple sequential search algorithm. The linear search is done sequentially to all elements in the list one by one. The type of searching algorithm is a basic searching algorithm that solves the problem of searching for a given element i in the array (Goodrich, & Tamassia, 2015, p.45). It works by traversing the array under search from the first element until the array member under search becomes found or not. Each element in the array is checked against the search item and if a match is found, that given array element is returned otherwise the search proceeds till the end of the list and returns -1 if the item is absent in that list (Ladd, 1998, p.34).

The Algorithm

Linear Search (Array Arr, Value =p)

Set i to 1

if i>n then go to step 7

if arr[i]= p then go to step 6

set i to i=1go to step 2

Print out the element p found at index i and go to step 8

Print item not found

Exit the algorithm

The Pseudocode

procedure linearsearch (array, value)

for each item in the array

if match item == value

return the location of the element

endif

end for

end procedure

The Java code for the linear search algorithm

Public class LinearSearchAlg

{

public static void main(String args[])

{

int c, n, search, array[];

Scanner in = new Scanner(System.in);

System.out.println("Number of items in array");

n = in.nextInt();

array = new int[n];

System.out.println("Enter " + n + " integers");

for (c = 0; c < n; c++)

array[c] = in.nextInt();

System.out.println("Enter value to find");

search = in.nextInt();

for (c = 0; c < n; c++)

{

if (array[c] == search)

{

System.out.println(search + " found at index " + (c + 1) + ".");

break;

}

}

if (c == n)

System.out.println(search + " not found");

}

}

Analysis of Linear Search Algorithm

The Efficiency of the Linear Search Algorithm

One of the methods used to analyze this algorithm is through the measurement of the step count required for the algorithm to terminate. The size of the input data determines the step count. Also, the number of steps will depend on whether the item under search is in the array and even the array length. The table below compares the best case, the average case, and that worst-case scenario. If the item is not in the list, which falls under the worst-case scenario, there are two extra steps in the loop for the sentinel loop. The sentinel loop utilizes the while loop.

Case Scenarios

Case Comparisons for N=10000 Comparisons in terms of N

Best case (Search item is the first in the list) 1(If the array element is in the first location) 1

Worst case (Search item is the last in the list) 10,000(Search item is the last item in the list) N

Average case (When search item is at the center) 5,000(Search item is in the middle of the list) N/2

The Complexity of the Linear Search Algorithm and Invariants

The time complexity of the linear search is O(n) meaning that the number of elements in the array has direct proportionality to the time taken to search for an item (Shaffer, 1998, p.67). The loop invariant is 0<=c<n. Upon termination, if array[search] is found the loop ends and outputs the search index. Otherwise, if the number of items searched equal the array size, the output becomes 0. Linear search algorithm needs steps between 1 and n before finding the search element or before establishing the search item is not in the list, hence the step count will be n+12. Assuming that the array items are uniformly distributed, both the average and worst cases have a complexity of O(n) (Sedgewick,2007, 56).

Loop Variants

The loop variant is f(n,i)=n-i (Shaffer, & Shaffer, 2011, p.35). The function f(n,1) is a function that has its integer decreasing after each loop since i increases after every loop. When F(n,1)=0 and i=n, the loop terminates and in the worst case the loop terminates when in.

Preconditions and Postconditions for the Linear Search

Preconditions:

An array arr of length n that stores items of some type; for some n1 where n is an integer.

A search item of some type that may be in array arr.Postcondition: An integer such that 0i>n and Arr[i]=search item.

The exception to being handled: An exception thrown if the item could not trace location in the list under the search

Comparing the Linear Search Algorithm to the Binary Search Algorithm

A binary search algorithm is much better and efficient because the list under search comes sorted hence taking less time to search for the element. Also, the time complexity of binary search algorithm is O(log2n) and its best case that occurs when the search element is at cethe nter of the array list and has a complexity of O(1). The linear search has its best case occurs when the search element is at the first index and has a complexity of O(1). (Shaffer, 1998, p.69).

References

Goodrich, M. T., & Tamassia, R. (2015). Data structures and algorithms in Java. New York, John Wiley.

Sedgewick, R. (2007). Algorithms in Java. Pt. 1-4 Pt. 1-4. Boston, Mass. [u.a.], Addison-Wesley.

Shaffer, C. A., & Shaffer, C. A. (2011). Data structures & algorithm analysis in Java. Mineola, NY, Dover Publications.

Shaffer, C. A. (1998). A practical introduction to data structures and algorithm analysis.

Ladd, S. R. (1998). Java algorithms. New York, McGraw-Hill. http://search.ebscohost.com/login.aspx?direct=true&scope=site&db=nlebk&db=nlabk&AN=1892.