Linear search

Linear search or sequential search is a simple search algorithm for finding a target within a list. In this type of search, a sequential search checks every element within the list for a target value till a match is found. Otherwise, the search continues until the end of the list.

In the best case, the complexity of this algorithm is O(1) in the worst case, is O(n).

1. Algorithm

Linear Search ( Array A, Value x)

Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Return Element x Found at index i and go to step 8
Step 7: Return -1
Step 8: Exit

2. Java Code

/**
* Simple Linear Search
* Complexity of the algorithm
* Best: O(1)
* Worst: O(n)
*/
public static int linearSearch(int[] array, int val){

    for (int i = 0; i < array.length; i++) {
        int num = array[i];
        if(val == num){
            return i;
        }
     }
     return -1;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s