Array Search

Searching an array means finding whether a value is present and, usually, where. Java offers two fundamental approaches: linear search, which checks elements one by one and works on any array, and binary search, which repeatedly halves a sorted array and is dramatically faster on large data. Choosing between them depends on whether the data is sorted and how often you search it.

Linear Search

A linear search examines each element in turn until it finds a match or reaches the end:

static int indexOf(int[] values, int target) {
    for (int i = 0; i < values.length; i++) {
        if (values[i] == target) {
            return i;            // found: stop immediately
        }
    }
    return -1;                   // not found
}

int[] ids = {104, 221, 387, 450, 512};
System.out.println(indexOf(ids, 387));   // 2
System.out.println(indexOf(ids, 999));   // -1

Returning -1 for "not found" is a convention, because -1 can never be a valid index.

Characteristics:

• Works on unsorted data.
• Takes time proportional to the array length, O(n). On average it checks half the elements; in the worst case (missing value) it checks all of them.
• Can search on any condition, not just equality.

Searching objects

For objects, compare with equals, never ==:

static int indexOf(String[] items, String target) {
    for (int i = 0; i < items.length; i++) {
        if (items[i].equals(target)) return i;
    }
    return -1;
}

== compares references, so it would miss a String with the same characters that happens to be a different object. If the array may contain null, use Objects.equals(items[i], target).

Searching by condition

A linear search can look for the first element satisfying any rule:

record Order(String id, String status, double amount) { }

static Order firstLargePending(Order[] orders) {
    for (Order o : orders) {
        if (o.status().equals("PENDING") && o.amount() > 10_000) {
            return o;
        }
    }
    return null;
}

Finding all matches

To collect every match rather than the first, keep looping and gather results:

static List<Integer> allIndexes(int[] values, int target) {
    List<Integer> found = new ArrayList<>();
    for (int i = 0; i < values.length; i++) {
        if (values[i] == target) found.add(i);
    }
    return found;
}

System.out.println(allIndexes(new int[]{3, 7, 3, 9, 3}, 3));   // [0, 2, 4]

Built-in Linear Search Helpers

The JDK has no Arrays.indexOf for primitive arrays, but several tools perform linear searches for you:

String[] cities = {"Chennai", "Mumbai", "Delhi"};

// Object arrays: view as a List
int pos = Arrays.asList(cities).indexOf("Delhi");                 // 2
boolean has = Arrays.asList(cities).contains("Pune");             // false

// Any array: streams
int[] marks = {78, 42, 91, 35};
boolean anyFail = Arrays.stream(marks).anyMatch(m -> m < 40);     // true
OptionalInt firstFail = Arrays.stream(marks).filter(m -> m < 40).findFirst();   // OptionalInt[35]

Arrays.asList does not copy the array; it wraps it in a fixed-size List view, so indexOf and contains search the original array directly. It works only for object arrays: Arrays.asList(intArray) produces a list containing one element, the int[] itself.

Binary Search

Binary search works only on a sorted array. It compares the target with the middle element and discards the half that cannot contain it, repeating until the target is found or nothing remains.

Search for 45 in [3, 12, 19, 27, 45, 58, 66, 81]

low=0, high=7  mid=3  value 27 < 45  → search right half
low=4, high=7  mid=5  value 58 > 45  → search left half
low=4, high=4  mid=4  value 45 = 45  → found at index 4

Three comparisons instead of five. The advantage grows quickly with size:

Each step halves the remaining range, so binary search takes O(log n) time.

Arrays.binarySearch

int[] sorted = {3, 12, 19, 27, 45, 58, 66, 81};

System.out.println(Arrays.binarySearch(sorted, 45));   // 4
System.out.println(Arrays.binarySearch(sorted, 3));    // 0

Overloads exist for every primitive type and for objects, plus versions that search a sub-range: Arrays.binarySearch(array, fromIndex, toIndex, key).

Understanding the return value when not found

When the key is missing, binarySearch does not simply return -1. It returns -(insertionPoint) - 1, where the insertion point is the index at which the key would be inserted to keep the array sorted:

int[] a = {10, 20, 30, 40};

Arrays.binarySearch(a, 25);   // -3  → insertion point 2 (between 20 and 30)
Arrays.binarySearch(a, 5);    // -1  → insertion point 0 (before everything)
Arrays.binarySearch(a, 50);   // -5  → insertion point 4 (after everything)

To recover the insertion point from a negative result:

int result = Arrays.binarySearch(a, 25);
if (result < 0) {
    int insertionPoint = -result - 1;    // 2
}

The extra - 1 guarantees that every "not found" result is negative, even when the insertion point is 0. A result of 0 therefore always means "found at index 0".

The insertion point is useful in its own right: it tells you where a value falls among sorted boundaries, which the practical example below uses.

Rules and pitfalls

• The array must be sorted in ascending order (or by the same comparator you pass). On an unsorted array, the result is undefined: it may return a wrong index or claim the value is missing.
• Sort with the same ordering you search with. If you sort with String.CASE_INSENSITIVE_ORDER, search with it too.
• Duplicates: if the key appears more than once, there is no guarantee which matching index is returned.
• Sorting cost: sorting takes O(n log n). For a single search on unsorted data, a linear scan is cheaper. Binary search pays off when you sort once and search many times.

Binary search on objects

String[] names = {"Linus", "Ada", "Grace", "Alan"};
Arrays.sort(names);                                    // [Ada, Alan, Grace, Linus]
System.out.println(Arrays.binarySearch(names, "Grace"));   // 2

record Course(String code, String title) { }

Course[] courses = {
    new Course("CS101", "Java Basics"),
    new Course("CS205", "Data Structures"),
    new Course("DV110", "Docker")
};                                                     // already sorted by code

Comparator<Course> byCode = Comparator.comparing(Course::code);
int i = Arrays.binarySearch(courses, new Course("CS205", null), byCode);
System.out.println(courses[i].title());               // Data Structures

The search key is a Course object whose only meaningful field is the code, because the comparator looks at nothing else.

Writing binary search yourself

Understanding the algorithm helps when you need a variation, such as finding the first occurrence of a duplicate:

static int binarySearch(int[] a, int key) {
    int low = 0, high = a.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;    // avoids int overflow of (low + high)
        if (a[mid] < key)      low = mid + 1;
        else if (a[mid] > key) high = mid - 1;
        else                   return mid;
    }
    return -(low + 1);                       // same convention as Arrays.binarySearch
}

low + (high - low) / 2 instead of (low + high) / 2 prevents overflow when both indexes are large, a bug that existed for years in many widely used libraries.

Comparing Arrays: mismatch

Arrays.mismatch finds the first index where two arrays differ, or returns -1 if they are equal:

int[] expected = {1, 2, 3, 4};
int[] actual   = {1, 2, 9, 4};
System.out.println(Arrays.mismatch(expected, actual));   // 2

This is handy in tests and when comparing versions of data.

Searching a 2D Array

A 2D array is searched with nested loops; returning from a helper method exits both loops at once:

static int[] find(char[][] grid, char target) {
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[r].length; c++) {
            if (grid[r][c] == target) return new int[]{r, c};
        }
    }
    return null;
}

Choosing a Search Strategy

For data that is searched by key over and over, especially when it also changes, a hash-based collection usually beats both kinds of array search. Those collections are covered later in this section.

Practical Example: Shipping Rate Slabs

A courier charges by weight slab: up to 0.5 kg, up to 1 kg, up to 2 kg, and so on. Given a parcel's weight, the program must find the first slab whose limit is at least that weight. The insertion point from binarySearch gives exactly that.

import java.util.Arrays;

public class ShippingRates {
    static final double[] SLAB_LIMITS_KG = {0.5, 1, 2, 5, 10, 20};
    static final int[] SLAB_PRICE_INR   = {40, 60, 90, 150, 260, 450};

    static int priceFor(double weightKg) {
        if (weightKg <= 0) throw new IllegalArgumentException("weight must be positive");
        int i = Arrays.binarySearch(SLAB_LIMITS_KG, weightKg);
        int slab = i >= 0 ? i : -i - 1;                // exact limit, or first limit above it
        if (slab == SLAB_LIMITS_KG.length) {
            return -1;                                 // heavier than every slab
        }
        return SLAB_PRICE_INR[slab];
    }

    public static void main(String[] args) {
        double[] parcels = {0.3, 1.0, 1.2, 7.5, 20.0, 25.0};
        for (double w : parcels) {
            int price = priceFor(w);
            System.out.printf("%5.1f kg -> %s%n", w, price < 0 ? "freight quote needed" : "INR " + price);
        }
    }
}

Output:

  0.3 kg -> INR 40
  1.0 kg -> INR 60
  1.2 kg -> INR 90
  7.5 kg -> INR 260
 20.0 kg -> INR 450
 25.0 kg -> freight quote needed

SLAB_LIMITS_KG is sorted, so binary search applies. When the weight equals a limit exactly (1.0 kg, 20.0 kg), the search returns that limit's index. Otherwise it returns a negative value, and -i - 1 converts it to the insertion point: the index of the first limit greater than the weight. For 1.2 kg the insertion point is 2 (the 2 kg slab). An insertion point equal to the array length means the parcel is heavier than every slab. The parallel array SLAB_PRICE_INR then gives the price for the slab index. With six slabs a linear scan would be just as fast, but the same code works unchanged for thousands of boundaries, such as tax brackets, postal codes, or IP address ranges.