Using TheAlgorithms Java BinarySearch for Sorted Lists

Quick answer

To search a sorted list with TheAlgorithms Java library, call the static method BinarySearch.binarySearch(list, key, comparator). It returns the zero‑based index of key if present, or a negative insertion point (-(insertionPoint) - 1) if absent, mirroring the contract of java.util.Collections.binarySearch.

How it works – a worked example

The following snippet shows a complete, minimal setup that you can paste into a Java project that includes the TheAlgorithms source (e.g., by adding its src/main/java folder as a source set). No additional dependencies are required.

import com.thealgorithms.searches.BinarySearch;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class BinarySearchDemo {
    public static void main(String[] args) {
        // 1. Create a sorted list of Integer objects
        List numbers = new ArrayList<>();
        Collections.addAll(numbers, 2, 5, 8, 12, 16, 23, 42);
        
        // 2. Define the key we are looking for
        Integer key = 16;
        
        // 3. Use natural ordering (Integer implements Comparable)
        int index = BinarySearch.binarySearch(numbers, key, Comparator.naturalOrder());
        
        // 4. Interpret the result
        if (index >= 0) {
            System.out.println("Found " + key + " at index " + index);
        } else {
            int insertionPoint = -index - 1;
            System.out.println("Not found. Insert at index " + insertionPoint + " to keep order");
        }
    }
}

When you run this program with JDK 8 or later, the output will be:

Found 16 at index 4

If you change key to a value not in the list, say 10, the program prints:

Not found. Insert at index 3 to keep order

The negative return value encodes the insertion point, allowing you to maintain sorted order when adding new elements.

Mechanism behind the method

The implementation follows the classic binary search algorithm:

1. It keeps two pointers, low and high, that delimit the current search range.
2. At each step it computes mid = low + (high - low) / 2 and retrieves list.get(mid).
3. The element at mid is compared to key using the supplied Comparator (or natural order if null).
4. Depending on the comparison, the search continues in the left or right half.
5. When the range empties (low > high), the loop ends and the method returns -(low) - 1, which is the insertion point formula.

Because the algorithm relies on list.get(index) being O(1), it achieves O(log n) time only when the underlying list supports random access (e.g., ArrayList, CopyOnWriteArrayList). With a sequential‑access list such as LinkedList, each get costs O(n), degrading the overall complexity to O(n log n).

Limits and common pitfalls

Precondition: the list must be sorted

The method assumes the list is already sorted according to the same comparator used in the call. Passing an unsorted list leads to undefined results; the returned index may be correct by coincidence, but you cannot rely on it. Always sort the list beforehand or guarantee it stays sorted.

Reference‑type requirement

The generic signature works only with reference types. Primitive values must be boxed (Integer, Double, etc.). Attempting to pass an int[] or a primitive collection will cause a compile‑time error.

Comparator consistency

If you supply a custom Comparator, ensure it is consistent with equals for the elements; otherwise the binary search logic may miss matches even when they exist.

Performance with non‑random‑access lists

Using LinkedList works functionally but is inefficient. For large datasets, prefer ArrayList or another random‑access list. You can verify the difference by timing the search with System.nanoTime on both list types; the LinkedList version will show noticeably higher latency.

Practical verification steps

1. Add the TheAlgorithms Java source to your project’s source paths.
2. Run the demo program above with a sorted ArrayList; confirm the printed index matches expectations.
3. Modify the list to be unsorted (e.g., shuffle it) and run the same call; observe that the returned value no longer corresponds to the true position.
4. Replace ArrayList with LinkedList and measure execution time with System.nanoTime for a large list (e.g., 1 million elements); you will see significantly higher elapsed time compared to the ArrayList case.

When to choose this implementation

Use TheAlgorithms BinarySearch when you already depend on the library for other algorithms and want a lightweight, dependency‑free search that mirrors the JDK’s contract. If you need only binary search and prefer the standard library, java.util.Collections.binarySearch is equivalent and requires no extra code.