COMP20010 Data Structures And Algorithms I

The Linear Search Algorithm

Linear search is a very commonly used searching method used by most programmers in order to search through a small list of elements. This kind of searching technique is also known as the Sequential Searching algorithm. It is an extremely simple searching algorithm, where a sequential search is conducted over all items in a list or array, one at a time. Every element is checked for equality with the being searched element and if a match is found then that particular element is displayed or returned. However, until the search element is spotted, the searching goes on till the pointer reaches the end of the list (Deitel and Deitel 2008).

Algorithm

LinearSearch (array myArray, value searchElement)

Step 1: Set index i to 0

Step 2: if i >= length(myArray) then go to step-7, else go to next step

Step 3: if myArray [i] = searchElement, then go to step-6, else go to next step

Step 4: Increment i by 1

Step 5: Go to Step-2

Step 6: Print searchElement ‘Found at index i and go to step-8’

Step 7: Print ‘element not found’

Step 8: Exit

Java Code for the Linear Search Algorithm

public class Search{

     public static int LinearSearch(int[] myArray, int searchElement){

        int flag=0;

        for(int i=0;i<myArray.length;i++){

            if(myArray[i[==searchElement){

                System.out.println(searchElement+" found at index "+i);

                return i;

            }

        }

        System.out.println(searchElement+" not found.”);

        return -1;

        }

     }

Efficiency

It is mathematically proven that the efficiency of a Linear Search algorithm is O(n), ‘n’ being the length of the array. This means that the loop counter has to traverse through the entire loop in order to search for a particular element that is probably present at the last index or may be is absent completely (Lafore 2017).

To analyse any algorithm, it is always necessary to consider the best case, the average case and the worst case scenario for that particular algorithm.

Considering the example below, the iteration comparisons can be easily made for the respective case scenarios.

Best Case Scenario

Suppose, for an array of length 10 with the following elements:

[ 15 , 12 , 16 , 20 , 45 , 33 , 19 , 25 , 30 , 10 ] and the element being searched for is 15.

Therefore, the element can be found with the linear search making the fewest comparisons at index 0 itself. Therefore, for best case scenario, the loop exits with only one iteration with a complexity of O(1).

Worst Case Scenario

Suppose, for an array of length 10 with the following elements:

[ 15 , 12 , 16 , 20 , 45 , 33 , 19 , 25 , 30 , 10 ] and the element being searched for is 10.

The element being present at the very end of the loop, in this case, the counter will have to iterate through the entire loop in order to spot the element being searched for. This gives the algorithm a complexity of O(10) as the loop has to go through 10 iterations. This would be the same if the item being searched for was absent from the array.

Therefore, it can be concluded that the Average Case iterations for the algorithm is N/2.

Loop Invariant

All values present in the array at a lower index than the present loop iterator index within the array, is not the value being searched (present searching index <= value index). Therefore, if an element is present multiple times, then the loop counter is surely expected to hit the first occurrence as index <= index of searched number.

Comparison with Binary Search

• The array list must be sorted in Binary Search but needs not to be so not in case of Linear Search.
• The linear search method sequentially searches a set of data, whereas Binary search uses a logical technique.
• The time complexity of linear search is O(n), whereas that for Binary search is  O(log n).
• The Linear search algorithm performs equality comparisons but the Binary search algorithm performs ordering comparisons.

References

Deitel, P.J. and Deitel, H.M., 2008. C++ how to Program. PearsonPrentice Hall.

Fletcher, R. and Reeves, C.M., 1964. Function minimization by conjugate gradients. The computer journal, 7(2), pp.149-154.

Glass, H. and Cooper, L., 1965. Sequential search: A method for solving constrained optimization problems. Journal of the ACM (JACM), 12(1), pp.71-82.

Lafore, R., 2017. Data structures and algorithms in Java. Sams Publishing.

Ravishankar, M., 1997, February. Some results on search complexity vs accuracy. In DARPA Speech Recognition Workshop (pp. 104-107). Morgan Kaufmann Pub.

Weiss, M.A. and Hartman, S., 1998. Data structures and problem solving using Java (Vol. 204). Boston, MA: Addison-Wesley.