☕ Java
Array Searching
Searching an array means finding the position of an element that satisfies a condition. The two fundamental strategies are linear search and binary search. Linear search examines every element in order — it works on any array regardless of order and runs in O(n) time. Binary search exploits a sorted order to eliminate half the remaining candidates with each comparison — it runs in O(log n) time but requires the array to be sorted. Understanding both algorithms, their implementation, their preconditions, and how Java's built-in Arrays.binarySearch() behaves is essential for writing correct and efficient array code. This entry covers both algorithms, the binary search contract, searching for multiple matches, and practical search patterns.
Linear Search — The Universal Baseline
Linear search is the simplest searching strategy: examine each element in turn until the target is found or all elements have been checked. It makes no assumption about the order of elements, works on any array, and has an O(n) worst-case time complexity. For small arrays (under ~20 elements), linear search is often faster than binary search in practice because binary search requires the overhead of a sorted array and computed mid-points. For large arrays where search is frequent, the O(log n) of binary search dramatically outperforms the O(n) of linear search.
Linear search expresses naturally in both indexed and stream forms. The indexed form returns the first matching index. The stream form can find any match, first or last, and can express complex conditions more cleanly. For reference types, use Objects.equals() or the type's own equals() rather than == to compare by value rather than by reference identity.
Linear search can be extended to find all matching indices, not just the first. This variant collects every matching position in a list. It is also the only option when searching for elements satisfying a predicate (elements greater than some value, elements matching a pattern) rather than exact equality.
Java
// ── Basic linear search — first matching index ───────────────────────
public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) return i; // found: return index
}
return -1; // not found: return -1 (convention)
}
int[] numbers = {15, 3, 42, 8, 27, 3, 19};
System.out.println(linearSearch(numbers, 8)); // 3
System.out.println(linearSearch(numbers, 99)); // -1
// ── Search reference types — use equals(), not == ─────────────────────
public static int searchStrings(String[] arr, String target) {
for (int i = 0; i < arr.length; i++) {
if (Objects.equals(arr[i], target)) return i;
}
return -1;
}
// ── Find all matching indices ─────────────────────────────────────────
public static List<Integer> findAll(int[] arr, int target) {
List<Integer> indices = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) indices.add(i);
}
return indices;
}
int[] withDuplicates = {15, 3, 42, 3, 27, 3, 19};
System.out.println(findAll(withDuplicates, 3)); // [1, 3, 5]
// ── Search by condition (predicate) ──────────────────────────────────
public static int findFirstGreaterThan(int[] arr, int threshold) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] > threshold) return i;
}
return -1;
}
// ── Stream-based search ───────────────────────────────────────────────
int[] data = {5, 12, 3, 28, 7, 41, 9};
// First element greater than 10
OptionalInt first = Arrays.stream(data)
.filter(n -> n > 10)
.findFirst();
System.out.println(first.getAsInt()); // 12
// Check if any element matches
boolean anyNegative = Arrays.stream(data).anyMatch(n -> n < 0);
boolean allPositive = Arrays.stream(data).allMatch(n -> n > 0);
// Collect all matching indices
List<Integer> matchingIndices = IntStream.range(0, data.length)
.filter(i -> data[i] > 10)
.boxed()
.collect(Collectors.toList());
System.out.println(matchingIndices); // [1, 3, 5]Binary Search — Exploiting Sorted Order
Binary search works on sorted arrays by maintaining a search interval [low, high] and comparing the middle element against the target. If the middle element equals the target, the search succeeds. If the middle element is less than the target, the target (if present) must be in the right half, so low advances past mid. If the middle element is greater than the target, the target must be in the left half, so high retreats before mid. Each comparison eliminates half the remaining candidates, producing O(log n) time complexity.
The implementation has a subtle correctness requirement: computing the middle index correctly. The naive formula (low + high) / 2 overflows when low + high exceeds Integer.MAX_VALUE. The correct formula is low + (high - low) / 2, which produces the same result without overflow. This was a famous bug in Java's standard library binary search for years before being fixed.
Binary search precondition: the array must be sorted in the same order as the comparison used. Calling binary search on an unsorted array produces undefined results — it will return some index or -1, but the result is meaningless. This precondition must be satisfied by the caller; the algorithm cannot detect or recover from an unsorted array.
Java
// ── Binary search implementation ─────────────────────────────────────
public static int binarySearch(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2; // overflow-safe mid
if (arr[mid] == target) return mid; // found
else if (arr[mid] < target) low = mid + 1; // target in right half
else high = mid - 1; // target in left half
}
return -1; // not found
}
// ── Binary search requires SORTED array ───────────────────────────────
int[] sorted = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
System.out.println(binarySearch(sorted, 7)); // 3
System.out.println(binarySearch(sorted, 15)); // 7
System.out.println(binarySearch(sorted, 6)); // -1
// ── Why overflow matters ──────────────────────────────────────────────
int low = 2_000_000_000, high = 2_100_000_000;
// int mid = (low + high) / 2; // 2_000_000_000 + 2_100_000_000 overflows!
int mid = low + (high - low) / 2; // safe: 2_000_000_000 + 50_000_000
// ── Step-by-step trace: search for 9 in [1,3,5,7,9,11,13,15,17,19] ───
// Step 1: low=0, high=9, mid=4, arr[4]=9 == 9 → FOUND at index 4
// ── Step-by-step trace: search for 6 ─────────────────────────────────
// Step 1: low=0, high=9, mid=4, arr[4]=9 > 6 → high=3
// Step 2: low=0, high=3, mid=1, arr[1]=3 < 6 → low=2
// Step 3: low=2, high=3, mid=2, arr[2]=5 < 6 → low=3
// Step 4: low=3, high=3, mid=3, arr[3]=7 > 6 → high=2
// Step 5: low=3 > high=2 → loop ends → return -1
// ── Performance comparison ────────────────────────────────────────────
// Array size: 1,000,000 sorted elements
// Linear search worst case: 1,000,000 comparisons
// Binary search worst case: log₂(1,000,000) ≈ 20 comparisons
// With 1,000 queries: linear = 1B comparisons, binary = 20K comparisonsArrays.binarySearch() — The Built-In Implementation
Arrays.binarySearch() is Java's built-in binary search that handles all array types and custom Comparators. Its return value contract is specific: if the element is found, it returns the index of a matching element (not necessarily the first or last if duplicates exist). If the element is not found, it returns -(insertion point) - 1, where the insertion point is the index where the element would be inserted to keep the array sorted.
The negative return value for not-found is a design choice that encodes additional information: the insertion point can be computed from the return value without an additional search. If binarySearch returns -5, then -(result) - 1 = 4, meaning the target would be inserted at index 4. This allows callers to efficiently find the right insertion position for maintaining a sorted array, or to determine which elements are less than and greater than the target.
For arrays with duplicate elements, Arrays.binarySearch() makes no guarantee about which duplicate it returns. It may return any one of the matching indices. If the first or last matching index is needed, a linear scan from the found index in the appropriate direction will locate it.
Java
// ── Arrays.binarySearch() — built-in ─────────────────────────────────
int[] sorted = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
// ── Found: returns the index ──────────────────────────────────────────
System.out.println(Arrays.binarySearch(sorted, 23)); // 5 — index of 23
System.out.println(Arrays.binarySearch(sorted, 2)); // 0 — first element
System.out.println(Arrays.binarySearch(sorted, 91)); // 9 — last element
// ── Not found: returns -(insertion point) - 1 ────────────────────────
// 10 would be inserted at index 2 (between 8 and 12)
int result = Arrays.binarySearch(sorted, 10);
System.out.println(result); // -3 (negative → not found)
System.out.println(-result - 1); // 2 (insertion point)
// 100 would be inserted at index 10 (after last element)
result = Arrays.binarySearch(sorted, 100);
System.out.println(result); // -11
System.out.println(-result - 1); // 10 (insert at end)
// ── Insertion point extraction ────────────────────────────────────────
public static int insertionPoint(int[] sortedArr, int value) {
int result = Arrays.binarySearch(sortedArr, value);
return result >= 0 ? result : -result - 1;
}
System.out.println(insertionPoint(sorted, 10)); // 2 — between 8 and 12
System.out.println(insertionPoint(sorted, 23)); // 5 — exact match position
System.out.println(insertionPoint(sorted, 100)); // 10 — after last element
// ── With duplicates — result index is not guaranteed ─────────────────
int[] withDups = {1, 3, 5, 5, 5, 7, 9};
int idx = Arrays.binarySearch(withDups, 5);
System.out.println(idx); // could be 2, 3, or 4 — any of the 5s
// Find FIRST occurrence of duplicate:
while (idx > 0 && withDups[idx - 1] == 5) idx--;
System.out.println("First 5 at: " + idx); // 2
// ── Searching object arrays with natural order ────────────────────────
String[] strings = {"apple", "cherry", "date", "fig", "mango"};
System.out.println(Arrays.binarySearch(strings, "date")); // 2
System.out.println(Arrays.binarySearch(strings, "kiwi")); // negative (not found)
// ── Searching with custom Comparator ─────────────────────────────────
String[] words = {"fig", "apple", "mango", "cherry", "date"};
Arrays.sort(words, Comparator.comparingInt(String::length));
// sorted by length: [fig, apple, mango, cherry, date]
// Wait — need consistent sort then search
Arrays.sort(words); // natural order for this example
int pos = Arrays.binarySearch(words, "cherry", Comparator.naturalOrder());
System.out.println(pos); // valid indexSearch Patterns and Practical Applications
Binary search generalises beyond exact match. The insertion point returned by Arrays.binarySearch() enables several practical patterns: finding the first element greater than a value (lower bound), finding the last element less than or equal to a value (upper bound), and determining if a value falls within a range. These patterns appear in database-style range queries, scheduling algorithms, and sorted data management.
A sorted array with binary search is a lightweight alternative to a TreeMap or TreeSet for read-heavy, write-rare scenarios. The array uses less memory, has better cache behaviour, and the binary search is extremely fast for large datasets. The trade-off is that insertion and deletion require shifting elements — O(n) — making sorted arrays unsuitable for frequent modification.
Java
// ── Lower bound: first index where arr[i] >= target ──────────────────
public static int lowerBound(int[] sortedArr, int target) {
int result = Arrays.binarySearch(sortedArr, target);
if (result >= 0) {
// Found — walk left to first occurrence
while (result > 0 && sortedArr[result - 1] == target) result--;
return result;
}
// Not found — insertion point is first element >= target
return -result - 1;
}
// ── Upper bound: first index where arr[i] > target ────────────────────
public static int upperBound(int[] sortedArr, int target) {
int result = Arrays.binarySearch(sortedArr, target);
if (result >= 0) {
// Found — walk right past last occurrence
while (result < sortedArr.length - 1
&& sortedArr[result + 1] == target) result++;
return result + 1;
}
return -result - 1;
}
int[] data = {1, 3, 5, 5, 5, 7, 9, 11};
System.out.println(lowerBound(data, 5)); // 2 — first index of 5
System.out.println(upperBound(data, 5)); // 5 — first index after all 5s
System.out.println(upperBound(data, 5) - lowerBound(data, 5)); // 3 — count of 5s
// ── Range query: count elements in [low, high] ────────────────────────
public static int countInRange(int[] sorted, int low, int high) {
int lo = lowerBound(sorted, low);
int hi = upperBound(sorted, high);
return Math.max(0, hi - lo);
}
System.out.println(countInRange(data, 3, 7)); // 5 — values 3,5,5,5,7
// ── Find insertion position to maintain sorted order ──────────────────
List<Integer> sortedList = new ArrayList<>(
List.of(1, 3, 5, 7, 9));
int valueToInsert = 6;
int insertAt = Collections.binarySearch(sortedList, valueToInsert);
if (insertAt < 0) insertAt = -insertAt - 1;
sortedList.add(insertAt, valueToInsert);
System.out.println(sortedList); // [1, 3, 5, 6, 7, 9]
// ── Check if value is in a sorted array (faster than contains) ────────
public static boolean containsSorted(int[] sorted, int value) {
return Arrays.binarySearch(sorted, value) >= 0;
}Related Topics in Arrays
Array Basics
An array in Java is a fixed-size, ordered collection of elements of the same type stored in a contiguous block of memory. Once created, the size of an array cannot change. Arrays are the simplest and most fundamental data structure in Java — they underlie many higher-level collections and provide direct, indexed access to elements in constant time O(1). Every array in Java is an object, inherits from java.lang.Object, and can hold either primitives or references.
One-Dimensional Array
A one-dimensional array is a linear sequence of elements of the same type, accessed by a single integer index. It is the simplest array form in Java and the foundation for understanding multidimensional arrays and collection classes. One-dimensional arrays are used to store and process lists of values — student grades, product prices, daily temperatures, character sequences — any time you need to work with a fixed-size ordered collection of homogeneous data.
Two-Dimensional Array
A two-dimensional array in Java is an array of arrays — each element of the outer array is itself a one-dimensional array. It is used to represent tabular data with rows and columns: matrices, game boards, spreadsheet grids, pixel buffers, and any data that is naturally organised in two dimensions. In Java, a 2D array is declared with two sets of brackets and accessed with two indices: array[row][column].
Multidimensional Array
A multidimensional array in Java is an array with more than two dimensions — an array of arrays of arrays, and so on. While two-dimensional arrays suffice for most programming tasks, three-dimensional arrays are used for spatial data (x, y, z coordinates of a 3D grid), volumetric data (layers, rows, columns), RGB pixel buffers, and scientific computations involving tensors. Java supports arbitrary dimensionality, though arrays beyond three dimensions are rare in practice.