Array Searching Problems
Solve one Java logic problem at a time, then flip for the complete explanation and program.
0/156
Known
filtered set
Solve one Java logic problem at a time, then flip for the complete explanation and program.
Java Logic Development · Chapter 10 Companion Article
Fourteen searching problems — linear and binary search, occurrence boundaries, rotated arrays, missing and duplicate values, and set-based comparisons — each chosen by asking what the data allows.
Array searching problems test how well you can locate, count, compare, and identify values inside arrays. Some problems require simple traversal, while others depend on sorted data, binary search, hashing, XOR, or index-based logic.
The correct technique depends mainly on:
| Problem Type | Main Technique | Typical Time |
|---|---|---|
| Unsorted search | Linear Search | O(n) |
| Sorted search | Binary Search | O(log n) |
| First/Last occurrence | Modified Binary Search | O(log n) |
| Count in sorted array | First + Last occurrence | O(log n) |
| Rotated sorted array | Modified Binary Search | O(log n) |
| Missing value | Arithmetic / XOR | O(n) |
| Single duplicate | Floyd's Cycle Detection | O(n) |
| Multiple duplicates | HashSet / Frequency Map | O(n) |
| Unique value | XOR | O(n) |
| Common values | HashSet | O(n + m) |
| Uncommon values | Set Difference | O(n + m) |
Linear search checks array elements one after another until the required element is found. It works with sorted arrays, unsorted arrays, primitive arrays, and small datasets where simplicity is more useful than optimization.
Find the index of a target element in an unsorted integer array.
Array: [24, 7, 18, 42, 11]
Target: 42Element found at index: 3Traverse the array from left to right. For every index i: compare array[i] with target. If they are equal, return i. If traversal finishes without a match, return -1. Returning immediately avoids unnecessary comparisons after the element is found.
public class LinearSearch {
public static void main(String[] args) {
int[] numbers = {24, 7, 18, 42, 11};
int target = 42;
int index = -1;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] == target) {
index = i;
break;
}
}
if (index != -1) {
System.out.println("Element found at index: " + index);
} else {
System.out.println("Element not found");
}
}
}Element found at index: 3| i | numbers[i] | Target | Match |
|---|---|---|---|
| 0 | 24 | 42 | No |
| 1 | 7 | 42 | No |
| 2 | 18 | 42 | No |
| 3 | 42 | 42 | Yes |
The loop stops at index 3.
O(1)O(n)O(1)Do not assume linear search returns all occurrences. This version intentionally stops at the first match.
Use linear search when the input is unsorted and preprocessing or sorting is not justified.
Binary search repeatedly divides the searchable portion of a sorted array into two halves. It requires the array to be sorted.
Search for a target value in a sorted array.
Array: [4, 9, 15, 21, 28, 36, 44]
Target: 28Element found at index: 4Maintain two indexes: low (beginning of the current search range) and high (end of the current search range). Calculate mid = low + (high - low) / 2. Then: if array[mid] equals target, return mid. If target is smaller, move high left. If target is larger, move low right.
public class BinarySearch {
public static void main(String[] args) {
int[] numbers = {4, 9, 15, 21, 28, 36, 44};
int target = 28;
int low = 0;
int high = numbers.length - 1;
int index = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (numbers[mid] == target) {
index = mid;
break;
} else if (numbers[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
if (index != -1) {
System.out.println("Element found at index: " + index);
} else {
System.out.println("Element not found");
}
}
}Element found at index: 4Initial:
low = 0
high = 6First middle:
mid = 3
numbers[3] = 2128 is greater than 21: low = 4. Next:
mid = 5
numbers[5] = 3628 is smaller: high = 4. Next:
mid = 4
numbers[4] = 28Target found.
O(1)O(log n)O(1) for iterative implementation.Applying binary search directly to an unsorted array produces unreliable results.
Prefer the overflow-safe middle calculation: int mid = low + (high - low) / 2;
A sorted array may contain duplicate values. Find the index where the target appears for the first time.
Array: [2, 5, 5, 5, 8, 12]
Target: 5First occurrence: 1Use binary search with one important modification. When target is found: store mid in result, then continue searching from low to mid - 1. This checks whether another occurrence exists at a smaller index.
public class FirstOccurrence {
public static void main(String[] args) {
int[] numbers = {2, 5, 5, 5, 8, 12};
int target = 5;
int low = 0;
int high = numbers.length - 1;
int result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (numbers[mid] == target) {
result = mid;
high = mid - 1;
} else if (numbers[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
System.out.println("First occurrence: " + result);
}
}First occurrence: 1First match may occur at index 2. Instead of stopping:
result = 2
high = 1Search continues on the left. Index 1 also contains 5: result = 1. No earlier 5 exists.
O(log n)O(1)Using ordinary binary search and assuming the returned matching index is the first occurrence.
Questions involving duplicate values often require modified binary search rather than standard binary search.
Find the final index where a target appears in a sorted array.
Array: [2, 5, 5, 5, 8, 12]
Target: 5Last occurrence: 3When array[mid] equals target: save mid, then set low = mid + 1. The search continues to determine whether the same value appears later.
public class LastOccurrence {
public static void main(String[] args) {
int[] numbers = {2, 5, 5, 5, 8, 12};
int target = 5;
int low = 0;
int high = numbers.length - 1;
int result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (numbers[mid] == target) {
result = mid;
low = mid + 1;
} else if (numbers[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
System.out.println("Last occurrence: " + result);
}
}Last occurrence: 3Target is found at index 2. Search continues right:
result = 2
low = 3Index 3 also contains 5: result = 3. No later matching value exists.
O(log n)O(1)Moving high to mid - 1 after finding the target would search for the first occurrence instead.
Count how many times a target occurs in a sorted array.
Array: [1, 3, 3, 3, 3, 7, 9]
Target: 3Occurrences: 4If first is the first index of target and last is the last index of target, then count = last - first + 1. This avoids scanning every duplicate.
public class CountOccurrences {
private static int findBoundary(int[] numbers, int target, boolean first) {
int low = 0;
int high = numbers.length - 1;
int result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (numbers[mid] == target) {
result = mid;
if (first) {
high = mid - 1;
} else {
low = mid + 1;
}
} else if (numbers[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
public static void main(String[] args) {
int[] numbers = {1, 3, 3, 3, 3, 7, 9};
int target = 3;
int first = findBoundary(numbers, target, true);
int last = findBoundary(numbers, target, false);
int count = first == -1 ? 0 : last - first + 1;
System.out.println("Occurrences: " + count);
}
}Occurrences: 4For target 3:
first = 1
last = 4Therefore:
count = 4 - 1 + 1
count = 4Two binary searches are performed:
O(log n)O(1)A linear scan can count occurrences in O(n), which is suitable when the array is unsorted.
When the interviewer explicitly says the array is sorted, look for an O(log n) solution before using a full traversal.
Determine whether an element exists in an ascending sorted array. Unlike the earlier binary-search example that returns an index, this variation focuses on a boolean membership check.
Array: [10, 20, 30, 40, 50, 60]
Target: 40Element exists: trueDiscard half of the remaining array after every comparison.
public class SearchSortedArray {
public static void main(String[] args) {
int[] numbers = {10, 20, 30, 40, 50, 60};
int target = 40;
int low = 0;
int high = numbers.length - 1;
boolean found = false;
while (low <= high) {
int mid = low + (high - low) / 2;
if (numbers[mid] == target) {
found = true;
break;
}
if (numbers[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
System.out.println("Element exists: " + found);
}
}Element exists: trueSuppose the middle element is 30 and the target is 40. Because the array is ascending, everything before 30 can also be discarded. Without sorted order, that conclusion would not be valid.
O(log n)O(1)Java also provides Arrays.binarySearch(), but implementing the algorithm manually is important for logic-development and interview questions.
A sorted array may be shifted around a pivot. Example:
Original: [1, 2, 3, 4, 5, 6, 7]
Rotated: [4, 5, 6, 7, 1, 2, 3]The complete array is no longer sorted, but at least one half around the middle remains sorted.
Search for a target in a rotated sorted array containing distinct values.
Array: [40, 50, 60, 70, 10, 20, 30]
Target: 20Element found at index: 5After calculating mid: check whether target equals array[mid]. Determine whether the left half is sorted. If target lies inside that sorted half, search there. Otherwise search the opposite half.
public class SearchRotatedArray {
public static void main(String[] args) {
int[] numbers = {40, 50, 60, 70, 10, 20, 30};
int target = 20;
int low = 0;
int high = numbers.length - 1;
int result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (numbers[mid] == target) {
result = mid;
break;
}
if (numbers[low] <= numbers[mid]) {
// Left half is sorted
if (target >= numbers[low] && target < numbers[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
} else {
// Right half is sorted
if (target > numbers[mid] && target <= numbers[high]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
}
System.out.println("Element found at index: " + result);
}
}Element found at index: 5Initial middle:
mid = 3
numbers[mid] = 70Left half [40, 50, 60, 70] is sorted. 20 does not lie between 40 and 70, so search right. New range: [10, 20, 30]. The target is found at original index 5.
O(log n) when values are distinct.O(1).Heavy duplication can make it difficult to determine which half is sorted. Some duplicate-aware versions may degrade toward O(n).
Do not sort the rotated array first unless the problem allows changing the complexity. Sorting would usually make the solution O(n log n).
An array contains distinct numbers from 1 to n, but exactly one number is missing. Find the missing number.
Array: [1, 2, 3, 5, 6]
Expected range: 1 to 6Missing element: 4The sum of numbers from 1 to n is n * (n + 1) / 2. Then missing = expectedSum - actualSum. For production code with large n, long should be used to reduce integer-overflow risk.
public class MissingElement {
public static void main(String[] args) {
int[] numbers = {1, 2, 3, 5, 6};
int n = 6;
long expectedSum = (long) n * (n + 1) / 2;
long actualSum = 0;
for (int number : numbers) {
actualSum += number;
}
long missing = expectedSum - actualSum;
System.out.println("Missing element: " + missing);
}
}Missing element: 4Expected: 1 + 2 + 3 + 4 + 5 + 6 = 21. Actual: 1 + 2 + 3 + 5 + 6 = 17. Difference: 21 - 17 = 4.
O(n)O(1)XOR can also find the missing value without arithmetic-sum overflow.
This formula works only when values belong to the expected 1 to n range, exactly one value is missing, and other values are not duplicated.
Using the arithmetic formula without verifying the input constraints.
An array contains n + 1 integers where every value is between 1 and n. Exactly one value is duplicated, although it may appear more than twice. Find that duplicate without modifying the array and using constant extra space.
[1, 3, 4, 2, 2]Duplicate element: 2Treat each array value as the index of the next node in a linked structure. Under the stated constraints, repeatedly following next = numbers[current] creates a cycle. The duplicate value acts as the entry point of that cycle.
Floyd's cycle detection uses slow (moves one step) and fast (moves two steps). After they meet, reset slow to the beginning. Move both one step at a time. Their next meeting point identifies the duplicate.
public class FindDuplicate {
public static void main(String[] args) {
int[] numbers = {1, 3, 4, 2, 2};
int slow = numbers[0];
int fast = numbers[0];
do {
slow = numbers[slow];
fast = numbers[numbers[fast]];
} while (slow != fast);
slow = numbers[0];
while (slow != fast) {
slow = numbers[slow];
fast = numbers[fast];
}
System.out.println("Duplicate element: " + slow);
}
}Duplicate element: 2Each valid array value points to another valid index. Because there are more positions than unique allowed values, at least one path must revisit a previously reached position. The repeated value creates the cycle entry.
O(n)O(1)This technique depends on strict constraints: array length is n + 1, every value is between 1 and n, and a duplicate is guaranteed. It is not a general-purpose duplicate finder for arbitrary integers.
This problem tests whether you can recognize a hidden linked-list/cycle structure inside an array.
An arbitrary array may contain several different duplicate values. Find every value that occurs more than once.
[4, 7, 2, 4, 9, 7, 7, 3, 2]Duplicate elements: [4, 7, 2]For each number: try to add it to seen. If seen.add() returns false, the number already exists, so add that number to duplicates. A LinkedHashSet preserves the order in which duplicate values are first detected.
import java.util.LinkedHashSet;
import java.util.Set;
public class MultipleDuplicates {
public static void main(String[] args) {
int[] numbers = {4, 7, 2, 4, 9, 7, 7, 3, 2};
Set seen = new LinkedHashSet<>();
Set duplicates = new LinkedHashSet<>();
for (int number : numbers) {
if (!seen.add(number)) {
duplicates.add(number);
}
}
System.out.println("Duplicate elements: " + duplicates);
}
} Duplicate elements: [4, 7, 2]After reading first 4: seen = [4]. Second 4:
4 already exists
duplicates = [4]Second 7: duplicates = [4, 7]. Second 2: duplicates = [4, 7, 2]. The third occurrence of 7 does not create another output entry because duplicates is also a set.
Average case:
O(n)O(n)Using only seen tells whether a value was encountered previously, but repeatedly printing on every repeated occurrence could produce duplicate output lines for a value appearing three times. The duplicates set keeps each duplicated value only once.
Every element appears exactly twice except one element that appears once. Find the unique value.
[6, 4, 9, 4, 6]Unique element: 9For any integer x:
x ^ x = 0
x ^ 0 = xXOR is also associative and commutative, so array order does not matter.
public class UniqueElement {
public static void main(String[] args) {
int[] numbers = {6, 4, 9, 4, 6};
int unique = 0;
for (int number : numbers) {
unique ^= number;
}
System.out.println("Unique element: " + unique);
}
}Unique element: 9Conceptually: 6 ^ 4 ^ 9 ^ 4 ^ 6. Rearrange equal pairs: (6 ^ 6) ^ (4 ^ 4) ^ 9. Therefore: 0 ^ 0 ^ 9 = 9.
O(n)O(1)The XOR solution requires every non-unique value to occur exactly twice. If values can occur arbitrary numbers of times, use frequency counting instead.
When a problem says "all elements occur twice except one", XOR should be one of the first techniques considered.
Find elements whose frequency is greater than one and display how many times each repeated value occurs. This differs from simply detecting duplicates because the frequency itself is required.
[5, 8, 5, 2, 8, 8, 4]5 repeated 2 times
8 repeated 3 timesA frequency map represents data such as:
5 -> 2
8 -> 3
2 -> 1
4 -> 1Only entries with frequency greater than 1 are repeated.
import java.util.LinkedHashMap;
import java.util.Map;
public class RepeatedElements {
public static void main(String[] args) {
int[] numbers = {5, 8, 5, 2, 8, 8, 4};
Map frequency = new LinkedHashMap<>();
for (int number : numbers) {
frequency.put(number, frequency.getOrDefault(number, 0) + 1);
}
for (Map.Entry entry : frequency.entrySet()) {
if (entry.getValue() > 1) {
System.out.println(entry.getKey() + " repeated " + entry.getValue() + " times");
}
}
}
} 5 repeated 2 times
8 repeated 3 timesHashMap does not guarantee insertion order. LinkedHashMap makes the displayed order predictable and follows the order in which distinct values first appear.
Average case:
O(n)O(n)If values belong to a small known range, an integer frequency array can be faster and lighter than a map.
Find distinct elements that appear in both arrays.
First: [3, 5, 7, 9, 11]
Second: [2, 5, 8, 9, 12]Common elements: [5, 9]Build a lookup set from the first array. For every value in the second array: check whether it exists in the lookup set, and if yes, add it to the result set. A result set prevents duplicate output.
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
public class CommonElements {
public static void main(String[] args) {
int[] first = {3, 5, 7, 9, 11};
int[] second = {2, 5, 8, 9, 12};
Set lookup = new HashSet<>();
Set common = new LinkedHashSet<>();
for (int number : first) {
lookup.add(number);
}
for (int number : second) {
if (lookup.contains(number)) {
common.add(number);
}
}
System.out.println("Common elements: " + common);
}
} Common elements: [5, 9]Lookup after first array: [3, 5, 7, 9, 11]. Check second array: 2 (absent), 5 (present), 8 (absent), 9 (present), 12 (absent). Result: [5, 9].
Average case:
O(n + m)O(n + k) where k is the number of distinct common values stored in the result.With two sorted arrays, a two-pointer solution can find common elements in O(n + m) without building a full lookup set.
Nested loops require O(n × m) comparisons and are unnecessary when extra memory is permitted.
Find distinct values that occur in exactly one of two arrays. This is the symmetric difference of the two sets.
First: [1, 2, 3, 4]
Second: [3, 4, 5, 6]Uncommon elements: [1, 2, 5, 6]Create a set for each array. Then: add values from first that are absent from second, and add values from second that are absent from first.
import java.util.LinkedHashSet;
import java.util.Set;
public class UncommonElements {
public static void main(String[] args) {
int[] first = {1, 2, 3, 4};
int[] second = {3, 4, 5, 6};
Set firstSet = new LinkedHashSet<>();
Set secondSet = new LinkedHashSet<>();
Set uncommon = new LinkedHashSet<>();
for (int number : first) {
firstSet.add(number);
}
for (int number : second) {
secondSet.add(number);
}
for (int number : firstSet) {
if (!secondSet.contains(number)) {
uncommon.add(number);
}
}
for (int number : secondSet) {
if (!firstSet.contains(number)) {
uncommon.add(number);
}
}
System.out.println("Uncommon elements: " + uncommon);
}
} Uncommon elements: [1, 2, 5, 6]First set: [1, 2, 3, 4]. Second set: [3, 4, 5, 6]. Only in first: [1, 2]. Only in second: [5, 6]. Combined: [1, 2, 5, 6].
Average case:
O(n + m)O(n + m)Common elements are the intersection: A ∩ B. Uncommon elements are the symmetric difference: values in A or B, but not both.
| Feature | Linear Search | Binary Search |
|---|---|---|
| Sorted input required | No | Yes |
| Basic time complexity | O(n) | O(log n) |
| Works naturally on unsorted data | Yes | No |
| Implementation complexity | Simple | Moderate |
| Best for small arrays | Yes | Yes |
| Efficient for large sorted arrays | Less efficient | Yes |
| Random access useful | Not required | Required for efficient array implementation |
For a sorted array [2, 4, 4, 4, 4, 8] and target 4, results are:
First occurrence = 1
Last occurrence = 4
Count = 4 - 1 + 1 = 4The key difference appears after finding the target. For first occurrence: high = mid - 1. For last occurrence: low = mid + 1.
These terms are related but not identical.
A value appearing more than once. Example: [1, 2, 3, 2]. Duplicate: 2.
Several different values appear more than once. Example: [1, 2, 1, 3, 2, 4]. Duplicates: 1, 2.
Usually asks which values occur repeatedly, sometimes together with their frequency. Example: 7 repeated 3 times.
A value satisfying the specific uniqueness condition of the problem. Example: [3, 8, 3]. Unique element: 8. Always read the exact constraints before choosing an algorithm.
O(n) memory is acceptable.The problem has a special cancellation pattern such as every value occurring twice except one, or one number missing under appropriate constraints. Do not use XOR blindly when occurrence rules differ.
Binary search relies on ordering. Without sorting, choosing which half to discard is impossible.
This fails when the question asks for first occurrence, last occurrence, or number of occurrences.
An algorithm valid for one duplicate may not work when multiple distinct duplicates exist.
For common elements, duplicates, and frequency problems, sets or maps often reduce O(n²) logic to average O(n).
Search methods commonly use -1 to represent an invalid or missing index.
Use while (low <= high). Using only low < high can skip the final candidate unless the algorithm is specifically designed around that condition.
Prefer int mid = low + (high - low) / 2; instead of int mid = (low + high) / 2; The first version avoids overflow when indexes are very large.
HashSet does not guarantee iteration order. If output order matters, use an appropriate ordered structure such as LinkedHashSet.
The sum formula assumes a valid consecutive range and exactly one missing element.
Searching an empty array must safely return a not-found result rather than accessing index 0.
Array-searching programs should be tested with cases such as:
Only apply edge cases that match the problem's stated constraints.
| Problem | Preferred Technique | Time | Extra Space |
|---|---|---|---|
| Linear Search | Sequential traversal | O(n) | O(1) |
| Binary Search | Divide search range | O(log n) | O(1) |
| First Occurrence | Modified binary search | O(log n) | O(1) |
| Last Occurrence | Modified binary search | O(log n) | O(1) |
| Count Occurrences | Two boundary searches | O(log n) | O(1) |
| Sorted Array Search | Binary search | O(log n) | O(1) |
| Rotated Array Search | Modified binary search | O(log n) | O(1) |
| Missing Element | Sum or XOR | O(n) | O(1) |
| One Duplicate | Floyd's cycle detection | O(n) | O(1) |
| Multiple Duplicates | HashSet | O(n) average | O(n) |
| Unique Element | XOR | O(n) | O(1) |
| Repeated Elements | Frequency map | O(n) average | O(n) |
| Common Elements | HashSet | O(n + m) average | O(n) |
| Uncommon Elements | Set difference | O(n + m) average | O(n + m) |
Before writing code for an array-searching problem, identify:
These details usually determine the correct algorithm before coding begins.
After understanding the basic problems, useful interview variations include:
These variations reuse the core ideas from this chapter while changing the constraints, which is how array-searching questions are commonly made more challenging.