Linear Search in Java

Yasin Cakal

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};
    }
}

Data Structures and Algorithms with Java

Participants 704