Search Algorithms

A common task in programming is the search for an element in an array. Let's say we have an array:

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

and we need to find the position of element 10 or simply check if this element exists in the array.

Depending on the size of the data and performance requirements, various search algorithms can be used. Some of them include:

• Linear Search – O(n)
• Binary Search – O(log N)
• Jump Search – O(√N)
• Interpolation Search – O(log log N)
• Exponential Search – O(log N)

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

1. Linear Search

The simplest, but also the slowest algorithm. We iterate through the array and compare each element with the value we are looking for.

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.

2. Binary Search – Iterative Approach

This algorithm is more efficient but requires a sorted array. The idea is to divide the array in half, compare the middle element with the target, and reduce the search range accordingly.

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

    while (firstIndex <= lastIndex) {
        int middleIndex = (firstIndex + lastIndex) / 2;

        if (array[middleIndex] == elementToSearch) {
            return middleIndex;
        } else if (array[middleIndex] < elementToSearch) {
            firstIndex = middleIndex + 1;
        } else {
            lastIndex = middleIndex - 1;
        }
    }
    return -1;
}

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

3. Binary Search – Recursive Approach

The same logic as above, but implemented using recursion.

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

        if (array[middle] == elementToSearch) {
            return middle;
        }

        if (array[middle] > elementToSearch) {
            return recursiveBinarySearch(array, firstElement, middle - 1, elementToSearch);
        }

        return recursiveBinarySearch(array, middle + 1, lastElement, elementToSearch);
    }
    return -1;
}

Time complexity: O(log n)
Pros: shorter and simpler logic
Cons: risk of StackOverflow on large arrays (no tail recursion)

4. Jump Search

Suitable for sorted arrays. The algorithm skips a fixed number of elements (e.g., √n), then performs linear search within the 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(√n)
Best for: frequent searches in large sorted arrays

Conclusion

If you're looking for a universal and simple way to search – use Linear Search.
If your array is sorted – use Binary Search or Jump Search.
For more specific use cases, consider Interpolation Search or Exponential Search.

Note: Choosing the right algorithm depends on the data structure, array size, and required performance.

Курс 'Java для начинающих' на Udemy