Tuesday , February 28 2017
Home / Data Structures / Linear Search using Java

Linear Search using Java

There are basically two aspects of computer programming. One is data organization also commonly called as data structures. Till now we have seen about data structures and the techniques and algorithms used to access them. The other part of computer programming involves choosing the appropriate algorithm to solve the problem. Data structures and algorithms are linked each other. After developing programming techniques to represent
information, it is logical to proceed to manipulate it.

Searching is used to find the location where an element is available. There are two
types of search techniques. They are:
1. Linear or sequential search
2. Binary search

Linear Search:

The Linear Search is the simplest of all searching techniques. In this technique, an ordered or
unordered list will be searched one by one from the beginning until the desired element
is found. If the desired element is found in the list then the search is successful
otherwise unsuccessful.

Suppose there are ‘n’ elements organized sequentially on a List. The number of comparisons required to retrieve an element from the list, purely depends on where the element is stored in the list. If it is the first element, one comparison will do; if it is second element two comparisons are necessary and so on. On an average you need [(n+1)/2] comparison’s to search an element. If search is not successful, you would need ’n’ comparisons.

The time complexity of linear search is O(n).

Linear Search Algorithm:

Let array a[n] stores n elements. Determine whether element ‘x’ is present or not.


linearSearch(a[n], x){
            index = 0;
            flag = 0;
            while (index < n) {
                do {
                    if (x == a[index]) {
                        flag = 1;
                        break;
                    }
                    index++;
                }

            }
            if (flag == 1) {
                 //Data found  ;
            } else {
                 //data not found
            }
        }

Example:


import java.util.Scanner;

/**
 *
 * @author chandrashekhar
 */
public class LinearSearch {

    public static void main(String[] args) {
        int a[];
        Scanner s = new Scanner(System.in);
        System.out.println("Enter Size of an Array");
        int n = s.nextInt();
        a = new int[n];
        System.out.println("Enter " + n + " elements");
        for (int i = 0; i < n; i++) {
            a[i] = s.nextInt();
        }
        System.out.println("Enter Key element to Find");
        int key = s.nextInt();
        int position = linearSearch(a, key);
        if(position == -1){
            System.out.println("Element Not found");
        }else{
            System.out.println("Element Found at Position : "+position);
        }

    }

    public static int linearSearch(int a[], int key) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] == key) {
                return i + 1;
            }
        }
        return -1;
    }
    public static void display(int a[]){
        System.out.println("Array Elements Are");
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]+" ");
            
        }
    }
}

output:

Enter Size of an Array
5
Enter 5 elements
23
52
62
12
42
Enter Key element to Find
62
Element Found at Position : 3

About chandrashekhar

Hi Folks, you have reach this so far, that shows you like what you are learning. Then why don't you support us to improve for bettor tutorials by leaving your valuable comments and why not you keep in touch with us for latest updates on your favorite blog @ facebook , twitter , Or Google+ ,

Check Also

What is an Algorithm ?

An algorithm is a finite sequence of instructions, each of which has a clear meaning …

Leave a Reply

Your email address will not be published. Required fields are marked *