Step 4 of 6

67% Complete

Search Operation

Learn how to find elements in an ArrayList

The Search Operation

Search operations help you find elements in an ArrayList. There are several ways to search: by index, by value, by condition, or check for existence.

Common search operations include:

Finding an element by value (indexOf, lastIndexOf)
Getting an element by index (get)
Checking if an element exists (contains)
Finding elements that match a condition (stream, filter)

Access by Index (Get)

Access an element at a specific index. This is the fastest operation. Time complexity: O(1) - constant time random access.

Array Visualization

Size: 5 | Capacity: 10

[0]

[1]

[2]

[3]

[4]

[5]

—

[6]

—

[7]

—

[8]

—

[9]

—

Occupied

Available Capacity

Access by Index (Java)

ArrayList<String> list = new ArrayList<>();
list.add("Apple");   // index 0
list.add("Banana");  // index 1
list.add("Cherry");  // index 2
list.add("Date");    // index 3
 
// Get element at index 1
String fruit = list.get(1);
System.out.println(fruit);  // Output: Banana
 
// Check bounds before accessing
if (index >= 0 && index < list.size()) {
    String element = list.get(index);
}

Find Index by Value (indexOf)

Find the index of the first occurrence of a specific value. Time complexity: O(n) - must search through elements.

Find Index (Java)

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.add("Cherry");
list.add("Banana");
list.add("Date");
 
// Find index of first "Banana"
int index = list.indexOf("Banana");
System.out.println(index);  // Output: 1
 
// Element not found returns -1
int index2 = list.indexOf("Grape");
System.out.println(index2);  // Output: -1
 
// Find last occurrence
int lastIndex = list.lastIndexOf("Banana");
System.out.println(lastIndex);  // Output: 3

Check if Element Exists (Contains)

Check if a specific value exists in the ArrayList without getting the index. Time complexity: O(n) - searches through all elements.

Check Existence (Java)

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.add("Cherry");
 
// Check if element exists
if (list.contains("Banana")) {
    System.out.println("Banana found!");
} else {
    System.out.println("Banana not found!");
}
 
// Works with any object
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(10);
numbers.add(20);
numbers.add(30);
 
if (numbers.contains(20)) {
    System.out.println("20 is in the list");
}

Search with Conditions (Java Streams)

Find elements that match specific conditions using streams and filters. Time complexity: O(n) - must check each element against condition.

Conditional Search (Java)

ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(10);
numbers.add(20);
numbers.add(30);
numbers.add(40);
numbers.add(50);
 
// Find first even number
Integer firstEven = numbers.stream()
    .filter(n -> n % 2 == 0)
    .findFirst()
    .orElse(null);
System.out.println(firstEven);  // 10
 
// Find all numbers greater than 25
ArrayList<Integer> filtered = numbers.stream()
    .filter(n -> n > 25)
    .collect(ArrayList::new, List::add, List::addAll);
System.out.println(filtered);  // [30, 40, 50]
 
// Count elements matching condition
long count = numbers.stream()
    .filter(n -> n > 25)
    .count();
System.out.println(count);  // 3

Binary Search (Sorted List Only)

For sorted lists, binary search is much faster than linear search. Time complexity: O(log n) - much better than O(n).

Binary Search (Java)

ArrayList<Integer> sorted = new ArrayList<>();
sorted.add(10);
sorted.add(20);
sorted.add(30);
sorted.add(40);
sorted.add(50);
// List MUST be sorted for binary search to work
 
// Binary search for 30
int index = Collections.binarySearch(sorted, 30);
System.out.println(index);  // 2 (index of 30)
 
// Search for non-existent element
int index2 = Collections.binarySearch(sorted, 35);
System.out.println(index2);  // Negative value indicating not found
 
// IMPORTANT: Use only on sorted lists!
// For unsorted lists, use indexOf() or stream().filter()

Important: Binary search only works on sorted lists. For unsorted lists, use indexOf() or stream operations.

Practice Exercise

Time Complexity Summary

Operation	Time Complexity	Notes
Get by index	O(1)	Direct array access
indexOf()	O(n)	Linear search
contains()	O(n)	Linear search
Binary search (sorted)	O(log n)	Must be sorted first
Stream filter	O(n)	Flexible but slower

Key Takeaways

Get by index: O(1) - fastest way to access elements
Find by value: O(n) - must search linearly unless sorted
Binary search: O(log n) - but only works on sorted lists
Check existence: O(n) - no faster way without sorting