ISC Practicals and Theory - Linear Search (OOP)

Linear search checks the elements of an array one by one from the start until the required value is found or the array ends. This version is written as a class Search: a parameterised constructor stores the size and the key and creates the array, readArray() fills it, find() searches and showResult() prints the answer. It reports the position of the first occurrence of the key.

Definition

In a linear (sequential) search the key is compared with arr[0], arr[1], arr[2] and so on, and the search stops at the first element equal to the key. If every element has been compared without a match, the key is not present. It works on unsorted arrays.

For the array 5 9 5 1 9 3 and key 9, arr[0] = 5 does not match and arr[1] = 9 matches: the match is at index 1, which is position 2.

Position convention used here: find() returns the 1-based position (index + 1), and -1 means "not present".

Duplicates: find() uses break at the first match, so only the first occurrence is reported.

Size: the array holds 1 to 20 elements. Any other size is rejected with an error message.

Algorithm

1. main reads size. If it is not from 1 to 20, it prints an error message and stops.
2. main reads k, the number to search, and creates the object s with new Search(size, k). The constructor stores the size in n, the key in key and creates arr with n elements.
3. s.readArray(sc) reads the n elements with a for loop.
4. main calls s.find():
   • Set pos = -1.
   • Loop i from 0 to n - 1. If arr[i] == key, set pos = i + 1 and break.
   • Return pos.
5. s.showResult(p) prints the position if p is not -1, otherwise a "not present" message.

Note the input order for this program: size, then the number to search, then the elements.

Program

The constructor creates the array, readArray() reads the elements, find() returns the position of the first match (-1 if none) and showResult() prints the outcome.

import java.util.Scanner;

/**
 * Class Search stores a 1D array and finds the first position of a given value
 * with a linear (sequential) search.
 */
public class Search
{
    int n;       // size of the array
    int arr[];   // array holding the elements
    int key;     // value to be searched

    /**
     * Parameterised constructor: stores the size and the key and creates the array.
     * @param nn the number of elements
     * @param k  the value to be searched
     */
    Search(int nn, int k)
    {
        n = nn;
        key = k;
        arr = new int[n];
    }

    /**
     * Reads the n elements into the array.
     * @param sc the Scanner used to read input
     */
    void readArray(Scanner sc)
    {
        System.out.println("Enter the elements:");
        for (int i = 0; i < n; i++)   // one element per turn
            arr[i] = sc.nextInt();
    }

    /**
     * Searches for key from the start of the array, stopping at the first match.
     * With duplicate values, only the first occurrence is found.
     * @return the 1-based position of key, or -1 if it is not present
     */
    int find()
    {
        int pos = -1;                 // -1 means "not found" until a match is seen
        for (int i = 0; i < n; i++)
        {
            if (arr[i] == key)        // first match
            {
                pos = i + 1;          // convert 0-based index to 1-based position
                break;                // stop: later duplicates are ignored
            }
        }
        return pos;
    }

    /**
     * Prints the result of the search.
     * @param pos the value returned by find(); -1 means not found
     */
    void showResult(int pos)
    {
        if (pos == -1)
            System.out.println(key + " is not present in the array.");
        else
            System.out.println(key + " is present at position " + pos);
    }

    /**
     * main: reads the size and the key, creates the object and calls the methods.
     * @param args command line arguments (not used)
     */
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);   // Scanner for input
        System.out.print("Enter the number of elements (1 to 20): ");
        int size = sc.nextInt();               // size typed by the user
        if (size < 1 || size > 20)             // range check
        {
            System.out.println("Invalid input. Size must be from 1 to 20.");
            return;
        }
        System.out.print("Enter the number to search: ");
        int k = sc.nextInt();                  // value to be searched
        Search s = new Search(size, k);        // object of the class
        s.readArray(sc);
        int p = s.find();                      // position found (-1 if absent)
        s.showResult(p);
    }
}

Variable description table

Sample input and output

Enter the number of elements (1 to 20): 6
Enter the number to search: 9
Enter the elements:
5 9 5 1 9 3
9 is present at position 2

Enter the number of elements (1 to 20): 4
Enter the number to search: 7
Enter the elements:
8 2 6 4
7 is not present in the array.

Enter the number of elements (1 to 20): 1
Enter the number to search: 7
Enter the elements:
7
7 is present at position 1

Enter the number of elements (1 to 20): 0
Invalid input. Size must be from 1 to 20.

Dry run

Input: size = 6, k = 9, array 5 9 5 1 9 3.

The loop is left at i = 1, so the second 9 at index 4 is never examined. find() returns 2, p = 2 and showResult(2) prints 9 is present at position 2. This matches the real run for the first sample above.

Variations

1. All positions "Search a number in an array and print the positions of all its occurrences."
2. Count "Search a number in an array and print how many times it occurs."
3. Last occurrence "Search a number in an array and print the position of its last occurrence."
4. Binary search "Search a number in a sorted array using binary search."