Search Algorithms for Arrays in Java

A very common task in programming is the search for an element in an array. Suppose we have an array:

int[] array = {1, 5, 8, 10, 16, 20, ..., 100};

and we need to find the position (index) of element 10, or simply check whether such an element exists in the array.

Depending on the size of the data and performance requirements, different search algorithms are used. The main ones are:

• Linear Search — O(n)
• Binary Search — O(log n)
• Jump Search — O(sqrt n)
• Interpolation Search — O(log log n)
• Exponential Search — O(log n)

Let's take a closer look at the most popular ones with Java examples.

1. Linear Search

The simplest, but not the fastest method. We iterate over the array elements in order and compare each one with the target value. As soon as we find a match, we return the index; if we reach the end, we return -1.

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

Time complexity: O(n)
Best for: unsorted arrays and small datasets. This is the only method covered here that does not require the array to be sorted first.

2. Binary Search — Iterative Approach

A more efficient algorithm that works only with sorted arrays. The idea is to repeatedly split the array in half: take the middle element at index middleIndex and compare it with the target. If they are equal, the search is done. If the target is smaller than the middle element, we discard the right half; otherwise, the left half. We repeat until the element is found or the range becomes empty. If the element is not found, we return -1.

public static int binarySearch(int[] array, int elementToSearch) {
    int firstIndex = 0;
    int lastIndex = array.length - 1;

    // stop condition (element is not present)
    while (firstIndex <= lastIndex) {
        int middleIndex = (firstIndex + lastIndex) / 2;

        // if the middle element is the target, return its index
        if (array[middleIndex] == elementToSearch) {
            return middleIndex;
        }
        // if the middle element is smaller,
        // move the lower bound to middle + 1, dropping the left half
        else if (array[middleIndex] < elementToSearch) {
            firstIndex = middleIndex + 1;
        }
        // if the middle element is larger,
        // move the upper bound to middle - 1, dropping the right half
        else {
            lastIndex = middleIndex - 1;
        }
    }
    return -1;
}

Time complexity: O(log n)
Best for: sorted arrays.

3. Binary Search — Recursive Approach

The same idea, but implemented with recursion: at each step the method calls itself for the narrowed range.

public static int recursiveBinarySearch(int[] array, int firstElement, int lastElement, int elementToSearch) {
    // stop condition
    if (lastElement >= firstElement) {
        int middle = (lastElement + firstElement) / 2;

        // if the middle element is the target, return its index
        if (array[middle] == elementToSearch) {
            return middle;
        }

        // if the middle element is larger than the target,
        // recurse into the narrowed left range
        if (array[middle] > elementToSearch) {
            return recursiveBinarySearch(array, firstElement, middle - 1, elementToSearch);
        }

        // otherwise recurse into the narrowed right range
        return recursiveBinarySearch(array, middle + 1, lastElement, elementToSearch);
    }
    return -1;
}

Time complexity: O(log n)
Pro: shorter code, easier-to-read logic.
Con: the JVM does not perform tail-call optimization, so in theory a very deep call tree could cause a StackOverflowError. In practice the depth of binary search is only O(log n), so this is more of a quirk than a real risk.

4. Jump Search

Suitable for sorted arrays. The algorithm jumps ahead by a fixed number of elements (usually a step of √n) until it overshoots the target value, then performs a linear search inside the found block.

public static int jumpSearch(int[] array, int elementToSearch) {
    int arrayLength = array.length;
    int jumpStep = (int) Math.sqrt(array.length);
    int previousStep = 0;

    while (array[Math.min(jumpStep, arrayLength) - 1] < elementToSearch) {
        previousStep = jumpStep;
        jumpStep += (int) Math.sqrt(arrayLength);
        if (previousStep >= arrayLength) {
            return -1;
        }
    }

    while (array[previousStep] < elementToSearch) {
        previousStep++;
        if (previousStep == Math.min(jumpStep, arrayLength)) {
            return -1;
        }
    }

    if (array[previousStep] == elementToSearch) {
        return previousStep;
    }
    return -1;
}

Time complexity: O(sqrt n)
Best for: large sorted arrays where a "step back" is more expensive than a "step forward" (for example, when reading sequentially from a storage medium).

Built-in Java Tools: No Manual Implementation

In real-world code you rarely need to write your own algorithm — the standard library already ships proven solutions:

• Arrays.binarySearch(array, key) — binary search over a sorted array. Returns the index of the element, or a negative number if it is absent.
• For collections — list.indexOf(element) (linear search) and Collections.binarySearch(list, key).
• With the Stream API it is convenient to check for presence: IntStream.of(array).anyMatch(x -> x == key).

int[] array = {1, 5, 8, 10, 16, 20};
int index = Arrays.binarySearch(array, 10); // 3

Comparison of Algorithms

Conclusion

If you need a universal and simple approach and the array is small or unsorted, use linear search. If the array is sorted, binary search is almost always the best choice, while jump search wins in specific scenarios with expensive access to previous elements. For fine-tuning there are interpolation and exponential search.

Bottom line: the choice of algorithm depends on the data structure, the array size, and the performance requirements. In application code the standard Arrays.binarySearch is enough in most cases.