Java Program for Linear Search

Introduction

This tutorial shows how to perform linear search in Java. It starts with explaining what linear search does, followed by a program that finds the first position of a value, then explains a variant that finds every position, and finally explains a variant that searches an array of Strings.

How linear search works

Linear search is the simplest search. It starts at the first element, compares it with the value that is searched for, i.e. the key, and moves on to the next element until it finds the key or has looked at all elements. For the key 45 in the array 12, 45, 7, 99, 30: the first element, 12, is not 45, the second element is, so the search stops at index 1. If the key is not in the array, the search has to look at every element and then reports that it was not found.

Linear search works on every array, sorted or not. For large arrays that are sorted, binary searchClick to read: binary search is much faster, because every comparison reduces the remaining part of the array to be searched into half.

Java program for linear search

The search is a method that returns the index of the key, or -1 when the key is not in the array. -1 can never be an index, so the caller can tell the two cases apart:
Java program for linear search in an array
//LinearSearch.java
package com.javabrahman.generaljava;

import java.util.Scanner;

public class LinearSearch {

  static int linearSearch(int[] numbers, int key) {
    for (int i = 0; i < numbers.length; i++) {
      if (numbers[i] == key) {
        return i;                                  // found: the search ends at the first match
      }
    }
    return -1;                                     // all elements checked, no match
  }

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    System.out.print("Enter the number of elements: ");
    int count = scanner.nextInt();

    int[] numbers = new int[count];
    System.out.print("Enter the elements: ");
    for (int i = 0; i < count; i++) {
      numbers[i] = scanner.nextInt();
    }
    System.out.print("Enter the value to search for: ");
    int key = scanner.nextInt();

    int index = linearSearch(numbers, key);
    if (index >= 0) {
      System.out.println(key + " found at index " + index + " (position " + (index + 1) + ")");
    } else {
      System.out.println(key + " not found in the array");
    }
  }
}
 OUTPUT for different input values
Enter the number of elements: 6
Enter the elements: 12 45 7 99 30 45
Enter the value to search for: 45
45 found at index 1 (position 2)

Enter the number of elements: 6
Enter the elements: 12 45 7 99 30 45
Enter the value to search for: 100
100 not found in the array

Enter the number of elements: 1
Enter the elements: 5
Enter the value to search for: 5
5 found at index 0 (position 1)
Explanation of the code
  • linearSearch() checks numbers[i] == key for every index. At the first match, return i ends the method at once, so the rest of the array is not looked at. Methods that return valuesClick to read: Methods that return values are explained in their own tutorial.
  • When the loop ends without a match, the method returns -1.
  • The array holds 45 twice, at the indexes 1 and 5. The search stops at the first one, index 1. Index 1 is position 2, because positions are counted from 1 and indexes from 0, which is why the program prints index + 1 as well.
  • 100 is not in the array, so all six elements are checked and the result is -1. A one-element array that holds the key is found at index 0.

Variant 1 - finding every position of the search key

When the search key can appear more than once in the array, the search must not stop at the first match. The loop then runs over the whole array and prints every index where the key is found:
Linear search that finds every position of the key
//LinearSearchAll.java
package com.javabrahman.generaljava;

import java.util.Scanner;

public class LinearSearchAll {

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    System.out.print("Enter the number of elements: ");
    int count = scanner.nextInt();

    int[] numbers = new int[count];
    System.out.print("Enter the elements: ");
    for (int i = 0; i < count; i++) {
      numbers[i] = scanner.nextInt();
    }
    System.out.print("Enter the value to search for: ");
    int key = scanner.nextInt();

    StringBuilder positions = new StringBuilder();
    int matches = 0;
    for (int i = 0; i < numbers.length; i++) {
      if (numbers[i] == key) {
        positions.append(" ").append(i);
        matches++;
      }
    }
    if (matches == 0) {
      System.out.println(key + " not found in the array");
    } else {
      System.out.println(key + " found at index:" + positions);
      System.out.println("Number of occurrences: " + matches);
    }
  }
}
 OUTPUT for different input values
Enter the number of elements: 6
Enter the elements: 12 45 7 99 30 45
Enter the value to search for: 45
45 found at index: 1 5
Number of occurrences: 2

Enter the number of elements: 6
Enter the elements: 12 45 7 99 30 45
Enter the value to search for: 100
100 not found in the array
Explanation of the code
  • The elements and the key are read with a Scanner, as in the first program.
  • The loop has no return or break, so it always checks the whole array. For every element equal to the key, the index is appended to the StringBuilder positions, and the counter matches grows by one.
  • After the loop, matches tells the program whether the key was found at all, and doubles as the answer to "how often does the key occur". The indexes are collected first so that the message can be chosen after the loop: 45 is found at indexes 1 and 5, and 100 is not found.

Variant 2 - searching a String key in an array of Strings

The same search works for an array of names. The only difference is the comparison: Strings are compared with equals(), or equalsIgnoreCase() when upper and lower case should not matter:
Linear search in an array of Strings
//LinearSearchStrings.java
package com.javabrahman.generaljava;

import java.util.Scanner;

public class LinearSearchStrings {

  static int linearSearch(String[] names, String key) {
    for (int i = 0; i < names.length; i++) {
      if (names[i].equalsIgnoreCase(key)) {
        return i;
      }
    }
    return -1;
  }

  public static void main(String[] args) {
    String[] names = {"Alice", "Bob", "Charlie", "Diana"};
    Scanner scanner = new Scanner(System.in);
    System.out.print("Enter a name to search for: ");
    String key = scanner.next();

    int index = linearSearch(names, key);
    if (index >= 0) {
      System.out.println(key + " found at index " + index + ": " + names[index]);
    } else {
      System.out.println(key + " not found");
    }
  }
}
 OUTPUT for different input values
Enter a name to search for: bob
bob found at index 1: Bob

Enter a name to search for: DIANA
DIANA found at index 3: Diana

Enter a name to search for: Zed
Zed not found
Explanation of the code
  • The array names holds four names, and the name to search for is read with scanner.next().
  • The method linearSearch() checks the names one by one and returns the index of the first name that matches the key, or -1 when the loop ends without a match - the same logic as for numbers.
  • The comparison is equalsIgnoreCase(), which compares the text and ignores upper and lower case. So "bob" matches "Bob" and "DIANA" matches "Diana"; "Zed" is not in the array.

Summary

In this tutorial we looked how to perform a linear search in Java, beginning with a a basic linear search program in Java, followed by a variant of linear search that find every occurence of the given search key and finally ends with showing how to search an array of Strings in Java.