Java Searching Algorithms

A searching algorithm is a step-by-step way to find a value inside data. In Java, searching often means checking an array, list, or tree and returning where the value was found.

This lesson focuses on two common array searches: linear search and binary search. Linear search works on any order of data. Binary search is faster for large data, but it only works when the data is sorted.

Linear Search

Linear search checks each element one at a time from the beginning to the end. If the current element matches the target, the algorithm returns that index. If the loop finishes without a match, the value is not in the array.

Linear search is simple and reliable. It is a good choice when the array is small, when the data is not sorted, or when sorting first would be unnecessary work.

Linear Search Example

This program searches an unsorted array of scores. The method returns the index of the target value, or -1 if the value is not found.

public class Main {
    static int linearSearch(int[] values, int target) {
        for (int i = 0; i < values.length; i++) {
            if (values[i] == target) {
                return i;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] scores = {82, 95, 71, 88, 90};

        System.out.println("88 found at index " + linearSearch(scores, 88));
        System.out.println("100 found at index " + linearSearch(scores, 100));
    }
}

Output:

88 found at index 3
100 found at index -1

How Linear Search Works

The loop starts at index 0 and compares each array element with target. When the target is 88, the method finds it at index 3 and returns immediately. When the target is 100, the method checks every element and then returns -1.

Linear search has a time complexity of O(n), which means the number of checks can grow with the number of elements.

Binary Search

Binary search is a faster algorithm for sorted data. Instead of checking every element, it looks at the middle element and decides whether to continue searching the left half or the right half.

If the target is smaller than the middle value, binary search moves left. If the target is larger, it moves right. Each step removes about half of the remaining values from consideration.

Binary Search Example

This program searches a sorted array. The variables low and high mark the part of the array that is still being searched.

public class Main {
    static int binarySearch(int[] values, int target) {
        int low = 0;
        int high = values.length - 1;

        while (low <= high) {
            int middle = low + (high - low) / 2;

            if (values[middle] == target) {
                return middle;
            }

            if (target < values[middle]) {
                high = middle - 1;
            } else {
                low = middle + 1;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] numbers = {4, 9, 15, 23, 31, 42, 56};

        System.out.println("31 found at index " + binarySearch(numbers, 31));
        System.out.println("10 found at index " + binarySearch(numbers, 10));
    }
}

Output:

31 found at index 4
10 found at index -1

How Binary Search Works

For the target 31, binary search first checks the middle of the array. Because the array is sorted, it can safely ignore the half that cannot contain the target. It repeats this process until it finds the value at index 4.

Binary search has a time complexity of O(log n), which grows much more slowly than O(n). The tradeoff is that the data must already be sorted.

Choosing A Search

Algorithm	Data requirement	Best use
Linear search	Any order	Small or unsorted data
Binary search	Sorted order	Larger sorted arrays

Java also provides built-in searching helpers, such as Arrays.binarySearch(), but understanding the algorithm helps you know when it is safe to use.

Takeaway: use linear search when data is unsorted, and use binary search when sorted data lets you eliminate half the remaining values at each step.