ISC Practicals and Theory - Linear Search

Linear search (sequential search) finds a value in an array by checking the elements one by one from the start until the value is found or the array ends. It works on any array, sorted or not. This program, written in the main method alone, reads an array of 1 to 20 integers and a key, and prints the position of the first occurrence of the key, or a message saying that it is not found.

Definition

In a linear search, the key is compared with a[0], then a[1], then a[2] and so on. The search stops as soon as one element equals the key, or when all $n$ elements have been compared without a match.

• Array: 12 7 25 7 40, key 7. a[0] = 12 does not match, a[1] = 7 matches, so the search stops at index 1.
• Array: 10 20 30 40, key 35. All four elements are compared and none matches, so the key is not found.

Position convention used here: the program reports the 1-based position (index + 1), so the first element is position 1.

Duplicates: the loop stops at the first match, so only the first occurrence is reported; later equal values are never examined.

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

Algorithm

1. Read the number of elements n. If it is not from 1 to 20, print an error message and stop.
2. Read the n elements into the array a, then read the number to search, key.
3. Set pos = -1. For i from 0 to n - 1, compare a[i] with key. At the first match, set pos = i + 1 (the index is 0-based, the position is 1-based) and leave the loop.
4. If pos is still -1, print that the key is not found. Otherwise print the position.

Program

The single for loop in main checks the elements one by one and stops at the first match.

import java.util.Scanner;
public class LinearSearch
{
    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 n = sc.nextInt();                  // number of elements (1 to 20)
        if (n < 1 || n > 20)                   // range check
        {
            System.out.println("Invalid input. Size must be from 1 to 20.");
        }
        else
        {
            int a[] = new int[n];              // array that stores the elements
            System.out.println("Enter the elements:");
            for (int i = 0; i < n; i++)        // read each element
                a[i] = sc.nextInt();
            System.out.print("Enter the number to search: ");
            int key = sc.nextInt();            // value to be searched
            int pos = -1;                      // position of the key, -1 if it is not found
            for (int i = 0; i < n; i++)
            {
                if (a[i] == key)               // match found
                {
                    pos = i + 1;               // index i is 0-based, position is i + 1
                    break;                     // the first occurrence is enough
                }
            }
            if (pos == -1)
                System.out.println(key + " is not found in the array.");
            else
                System.out.println(key + " is found at position " + pos);
        }
    }
}

Variable description table

Sample input and output

Enter the number of elements (1 to 20): 5
Enter the elements:
12 7 25 7 40
Enter the number to search: 7
7 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 search: 35
35 is not found in the array.

Enter the number of elements (1 to 20): 1
Enter the elements:
9
Enter the number to search: 9
9 is found at position 1

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

Dry run

Input: n = 5, array 12 7 25 7 40, key = 7.

The loop stops at i = 1, so the second 7 at index 3 is never reached. so pos = 2 and the program prints 7 is found 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."