ISC Practicals and Theory - Linear Search (Recursive Technique) (OOP)

This version of recursive linear search is written as a class with a parameterised constructor and methods that each do one job: reading the array, searching recursively and displaying the result. The method search() calls itself with the next index until the key is found or the array ends.

Definition

Linear search compares the key with the elements of an array one by one from index 0 and stops at the first match, or at the end of the array when there is no match. For {4, 8, 15, 8, 23, 8} and key $8$, the first match is at index 1, so the position reported is 2.

Position convention used here: positions are reported 1-based (index + 1) and only the first occurrence is used when the key repeats. The array holds 1 to 20 elements; any other size is rejected with an error message.

Algorithm

1. main() reads the size size. If it is less than 1 or more than 20, it prints the invalid size message and stops.
2. main() reads the key k and creates the object with new LinearSearch(size, k). The constructor stores n and key and creates the array a of exactly n elements.
3. readArray() reads the n elements into a[].
4. search(0) is called:
   • Base case 1: if i == n, return $-1$ (key absent).
   • Base case 2: if a[i] == key, return i.
   • Recursive case: return search(i + 1).
5. display(p) prints the not found message if p is $-1$, otherwise position p + 1.

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

Program

The parameterised constructor builds the array, readArray() fills it, search() is the recursive method and display() prints the result.

import java.util.Scanner;

/**
 * Class LinearSearch searches a key in an integer array using recursion.
 * The array is created by a parameterised constructor.
 */
public class LinearSearch
{
    int a[];    // array that stores the numbers
    int n;      // size of the array
    int key;    // the number to be searched

    /**
     * Parameterised constructor: creates the array and stores the key.
     * Parameter size: number of elements, parameter k: number to be searched.
     */
    LinearSearch(int size, int k)
    {
        n = size;
        key = k;
        a = new int[n];       // array of exactly n elements
    }

    /**
     * Reads the n elements of the array.
     * Parameter sc: Scanner used to read from the keyboard.
     */
    void readArray(Scanner sc)
    {
        System.out.println("Enter the elements:");
        for (int i = 0; i < n; i++)   // read the elements one by one
            a[i] = sc.nextInt();
    }

    /**
     * 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
    }

    /**
     * Displays the position (1-based) of the key, or a not found message.
     * Parameter p: index returned by search().
     */
    void display(int p)
    {
        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: reads size and key, validates the size,
     * creates the object and calls the methods.
     */
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);   // reads input from the keyboard
        System.out.print("Enter the number of elements (1 to 20): ");
        int size = sc.nextInt();               // size of the array
        if (size < 1 || size > 20)             // size outside the allowed range
        {
            System.out.println("Invalid size. Size must be between 1 and 20");
            return;
        }
        System.out.print("Enter the number to be searched: ");
        int k = sc.nextInt();                  // key to be searched
        LinearSearch ob = new LinearSearch(size, k);   // object of the class
        ob.readArray(sc);
        int p = ob.search(0);                  // search starts from index 0
        ob.display(p);
    }
}

Variable description table

Sample input and output

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

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

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

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

Dry run

Input: size = 6, k = 8, elements 4 8 15 8 23 8. The calls go down to a base case and the value comes back up.

main() stores p = 1 and display(1) prints position 1 + 1 = 2: 8 is found at position 2. The later 8s are never checked.

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."