ISC Practicals and Theory - Linear Search (Recursive Technique)

Linear search finds a given number in an array by checking the elements one after another from the beginning. In the recursive technique, the method search() checks one element and then calls itself to check the rest of the array, until the number is found or the array ends.

Definition

Linear search (sequential search) compares the key with each element of the array in order, starting at index 0. It stops at the first element equal to the key, or after the last element if there is none.

For the array {4, 8, 15, 8, 23} and key $8$:

• The key is at index 1 (position 2) and again at index 3. The search stops at the first match, so the program reports position 2.

For the key $9$ every element is checked and none matches, so the key is not found.

Position convention used here: the program reports the 1-based position (index + 1), and for a repeated number only the first occurrence is reported. The array holds 1 to 20 elements; any other size is rejected with an error message.

Algorithm

1. Start. main() creates an object ob of class LinearSearch; the constructor creates the array a of 20 elements and sets n = 0.
2. input() reads n. If n is less than 1 or more than 20, it returns false and main() prints the invalid size message.
3. Otherwise input() reads the n elements into a[] and then the key, and returns true.
4. display() calls search(0), which works as follows:
   • Base case 1: if i == n, all elements are checked and the key is absent, so return $-1$.
   • Base case 2: if a[i] == key, return i.
   • Recursive case: otherwise return search(i + 1).
5. display() receives the value in p. If p is $-1$ it prints the not found message, otherwise it prints position p + 1.
6. Stop.

Program

The constructor sets up the array, input() accepts the data, search() is the recursive method and display() prints the result.

import java.util.Scanner;

/**
 * Class LinearSearch searches a key in an integer array
 * using a recursive linear search.
 */
public class LinearSearch
{
    int a[];    // array that stores the numbers entered by the user
    int n;      // number of elements actually stored in the array
    int key;    // the number to be searched

    /**
     * Default constructor: creates the array and initialises the data members.
     */
    LinearSearch()
    {
        a = new int[20];  // array can hold at most 20 elements
        n = 0;
        key = 0;
    }

    /**
     * Accepts the size, the elements and the key from the user.
     * Parameter sc: Scanner used to read from the keyboard.
     * Return type: boolean, true if the size is valid (1 to 20), otherwise false.
     */
    boolean input(Scanner sc)
    {
        System.out.print("Enter the number of elements (1 to 20): ");
        n = sc.nextInt();
        if (n < 1 || n > 20)      // size outside the allowed range
            return false;
        System.out.println("Enter the elements:");
        for (int i = 0; i < n; i++)   // read the elements one by one
            a[i] = sc.nextInt();
        System.out.print("Enter the number to be searched: ");
        key = sc.nextInt();
        return true;
    }

    /**
     * Recursively searches the key from index i onwards.
     * Parameter i: index at which the search currently stands.
     * Return type: int, index of the first occurrence of key, or -1 if absent.
     */
    int search(int i)
    {
        if (i == n)               // base case 1: whole array checked, key absent
            return -1;
        if (a[i] == key)          // base case 2: key found at index i
            return i;
        return search(i + 1);     // recursive case: look at the next element
    }

    /**
     * Calls search() and displays the position (1-based) of the key.
     */
    void display()
    {
        int p = search(0);        // search starts from index 0
        if (p == -1)
            System.out.println(key + " is not found in the array");
        else
            System.out.println(key + " is found at position " + (p + 1));
    }

    /**
     * main method: creates the object and calls the methods.
     */
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);   // reads input from the keyboard
        LinearSearch ob = new LinearSearch();  // object of the class
        if (ob.input(sc))
            ob.display();
        else
            System.out.println("Invalid size. Size must be between 1 and 20");
    }
}

Variable description table

Sample input and output

Enter the number of elements (1 to 20): 5
Enter the elements:
4 8 15 8 23
Enter the number to be searched: 8
8 is found at position 2

Enter the number of elements (1 to 20): 4
Enter the elements:
10 20 30 40
Enter the number to be searched: 25
25 is not found in the array

Enter the number of elements (1 to 20): 1
Enter the elements:
6
Enter the number to be searched: 6
6 is found at position 1

Enter the number of elements (1 to 20): 25
Invalid size. Size must be between 1 and 20

Dry run

Input: n = 5, elements 4 8 15 8 23, key = 8. The calls go down until a base case is reached, then the value returns up.

display() gets p = 1, prints p + 1 = 2, so the output is 8 is found at position 2. The second 8 (index 3) is never reached.

Variations

1. Iterative linear search "Write a program to search a number in an array using linear search with a loop."
2. Binary search, recursive "Write a program to search a number in a sorted array using binary search with recursion."
3. Count occurrences "Write a program to count how many times a number occurs in an array using recursion."
4. Search in a String array "Write a program to search a name in an array of names using linear search."