Linear search in Java

Remember, Linear search (or sequential search) is a simple algorithm for searching a value in arrays or similar collections. The algorithm checks each element of the array until it finds an element that matches the target value. If the algorithm reaches the end of the array, it terminates unsuccessfully. In the worst cases, it performs exactly N comparisons where N is the length of the input array containing data.

This algorithm can be also modified to check an array contain a target element, search for the first or last occurrences of an element, searching a value only in a range of indexes of the array or counting all occurrences of a target element.

The Java implementation

Let's consider the implementation of the algorithm in Java as a regular static method. The method takes an array of int's and a number to search in the array. It returns the index of the found element or -1.

public static int search(int[] array, int value) {
    int index = -1;
    for (int i = 0; i < array.length; i++) {
        if (array[i] == value) {
            index = i;
            break;
        }
    }
    return index;
}

As you can see, the implementation is very simple. It compares each element of an input array with the passed value in the loop. If an element is equal to the value, the loop stops and the method returns the found index. If no value is found in the array, the method returns the special value -1.

Let's call the method passing different arrays and values:

int[] numbers = {1, 4, 7, 2, 3, 5};

search(numbers, 1); // 0
search(numbers, 2); // 3
search(numbers, 3); // 4
search(numbers, 4); // 1
search(numbers, 5); // 5
search(numbers, 6); // -1, no value found

In the last sample, the algorithm returns -1 after checking all element of the array for equality 6.

Searching values in sorting arrays

Important, the considered algorithm works for both sorted and unsorted arrays. We can make the algorithm more "efficient" to search an element in a sorted array. This works only when we are sure the array is sorted.

public static int searchInSortedArray(int[] array, int value) {
    int index = -1;
    for (int i = 0; i < array.length; i++) {
        if (array[i] == value) {
            index = i;
            break;
        } else if (array[i] > value) {
           break;
        }
    }
    return index;
}

searchInOrderedArray(new int[] {8, 15, 19, 20, 21}, 10); // -1, the element 10 is not found