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");
}
}
}
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)
linearSearch()checksnumbers[i] == keyfor every index. At the first match,return iends 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 + 1as 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);
}
}
}
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
- The elements and the key are read with a
Scanner, as in the first program. - The loop has no
returnorbreak, so it always checks the whole array. For every element equal to the key, the index is appended to theStringBuilderpositions, and the countermatchesgrows by one. - After the loop,
matchestells 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");
}
}
}
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
- The array
namesholds four names, and the name to search for is read withscanner.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.General Java Programs on JavaBrahman
Fahrenheit to CelsiusClick to Read Fahrenheit to Celsius Tutorial FactorialClick to Read Factorial Tutorial FibonacciClick to Read Fibonacci Tutorial PalindromeClick to Read Palindrome Tutorial Armstrong NumberClick to Read Armstrong Number Tutorial Automorphic NumberClick to Read Automorphic Number Tutorial Harshad NumberClick to Read Harshad Number Tutorial Matrix AdditionClick to Read Matrix Addition Tutorial Matrix MultiplicationClick to Read Matrix Multiplication Tutorial
Fahrenheit to CelsiusClick to Read Fahrenheit to Celsius Tutorial FactorialClick to Read Factorial Tutorial FibonacciClick to Read Fibonacci Tutorial PalindromeClick to Read Palindrome Tutorial Armstrong NumberClick to Read Armstrong Number Tutorial Automorphic NumberClick to Read Automorphic Number Tutorial Harshad NumberClick to Read Harshad Number Tutorial Matrix AdditionClick to Read Matrix Addition Tutorial Matrix MultiplicationClick to Read Matrix Multiplication Tutorial