Linear search is a process of searching for an element in a given list of elements. The search begins at the beginning of the list and continues until either the element is found or the end of the list is reached. It is also referred to as a sequential search. Linear search is a simple and straightforward search algorithm that can be used to find an element in a list.
How Linear Search Works
Linear search works by starting at the beginning of the list and comparing each element in the list to the item that is being searched for. If the item is found, the search is successful and the index of the element is returned. If the item is not found, the search is unsuccessful and a null value is returned.
Linear search can be implemented using a for loop. The for loop will iterate through each element of the list and compare it to the item that is being searched for. If the item is found, the loop can be terminated early and the index of the element is returned. If the item is not found, the loop will continue until the end of the list is reached.
Java Code Example
The following Java code example demonstrates how to implement a linear search algorithm. The example searches through an array of integers for the value 13.
public class LinearSearch {
public static void main(String[] args) {
// array of integers to search
int[] numbers = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
// value to search for
int value = 13;
// search the array
int index = linearSearch(numbers, value);
// display the result
if (index == -1) {
System.out.println("Value not found!");
} else {
System.out.println("Value found at index: " + index);
}
}
// linear search algorithm
public static int linearSearch(int[] numbers, int value) {
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] == value) {
return i;
}
}
return -1;
}
}
Time Complexity
The time complexity of linear search is O(n), where n is the number of elements in the list. This means that the search time increases linearly with the number of elements in the list. Linear search has a best-case time complexity of O(1) if the item is found in the first element of the list. The average and worst-case time complexity of linear search is O(n).
Space Complexity
The space complexity of linear search is O(1). This means that the amount of memory used by the algorithm does not increase with the size of the list. Linear search requires only a few variables to store the list and the item that is being searched for.
Conclusion
Linear search is a simple and straightforward search algorithm that can be used to find an element in a list. It is implemented using a for loop that iterates through each element of the list and compares it to the item that is being searched for. The time complexity of linear search is O(n), with a best-case time complexity of O(1), and the space complexity is O(1).
Exercises
Write a linear search algorithm that searches an array of strings for a specified string.
public class LinearSearch {
public static void main(String[] args) {
// array of strings to search
String[] words = {"apple", "banana", "cherry", "date", "fig"};
// string to search for
String value = "date";
// search the array
int index = linearSearch(words, value);
// display the result
if (index == -1) {
System.out.println("String not found!");
} else {
System.out.println("String found at index: " + index);
}
}
// linear search algorithm
public static int linearSearch(String[] words, String value) {
for (int i = 0; i < words.length; i++) {
if (words[i].equals(value)) {
return i;
}
}
return -1;
}
}
Write a linear search algorithm that searches an array of objects for a specified object.
public class LinearSearch {
public static void main(String[] args) {
// array of objects to search
Person[] people = {
new Person("John", 30),
new Person("Mary", 25),
new Person("Bob", 28)
};
// object to search for
Person value = new Person("Bob", 28);
// search the array
int index = linearSearch(people, value);
// display the result
if (index == -1) {
System.out.println("Object not found!");
} else {
System.out.println("Object found at index: " + index);
}
}
// linear search algorithm
public static int linearSearch(Person[] people, Person value) {
for (int i = 0; i < people.length; i++) {
if (people[i].equals(value)) {
return i;
}
}
return -1;
}
}
// Person class
public class Person {
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public boolean equals(Object object) {
if (this == object) {
return true;
}
if (object == null || getClass() != object.getClass()) {
return false;
}
Person other = (Person) object;
return name.equals(other.name) && age == other.age;
}
}
Write a linear search algorithm that searches an array of integers for a specified integer and returns the number of comparisons performed.
public class LinearSearch {
public static void main(String[] args) {
// array of integers to search
int[] numbers = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
// integer to search for
int value = 14;
// search the array
int index = linearSearch(numbers, value);
int comparisons = linearSearchCount(numbers, value);
// display the result
if (index == -1) {
System.out.println("Value not found!");
} else {
System.out.println("Value found at index " + index + " after " + comparisons + " comparisons.");
}
}
// linear search algorithm
public static int linearSearch(int[] numbers, int value) {
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] == value) {
return i;
}
}
return -1;
}
// linear search algorithm with count
public static int linearSearchCount(int[] numbers, int value) {
int count = 0;
for (int i = 0; i < numbers.length; i++) {
count++;
if (numbers[i] == value) {
return count;
}
}
return -1;
}
}
Write a linear search algorithm that searches an array of integers for a specified integer and counts the number of times the specified integer appears in the array.
public class LinearSearch {
public static void main(String[] args) {
// array of integers to search
int[] numbers = {2, 4, 6, 8, 10, 12, 14, 16, 18, 14, 20};
// integer to search for
int value = 14;
// search the array
int count = linearSearchCount(numbers, value);
// display the result
if (count == 0) {
System.out.println("Value not found!");
} else {
System.out.println("Value found " + count + " times.");
}
}
// linear search algorithm with count
public static int linearSearchCount(int[] numbers, int value) {
int count = 0;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] == value) {
count++;
}
}
return count;
}
}
Write a linear search algorithm that searches a two-dimensional array of integers for a specified value and returns the position of the element.
public class LinearSearch {
public static void main(String[] args) {
// two-dimensional array of integers to search
int[][] numbers = {
{2, 4, 6, 8},
{10, 12, 14, 16},
{18, 20, 22, 24}
};
// value to search for
int value = 14;
// search the array
int[] index = linearSearch(numbers, value);
// display the result
if (index[0] == -1) {
System.out.println("Value not found!");
} else {
System.out.println("Value found at position (" + index[0] + ", " + index[1] + ").");
}
}
// linear search algorithm
public static int[] linearSearch(int[][] numbers, int value) {
for (int i = 0; i < numbers.length; i++) {
for (int j = 0; j < numbers[i].length; j++) {
if (numbers[i][j] == value) {
return new int[] {i, j};
}
}
}
return new int[] {-1, -1};
}
}