Data Collections Algorithms in Java: Searching, Sorting, and Recursion

Searching (in a collection)

The process of determining whether a target item exists in a data collection (like an array or ArrayList) and, if so, where it is located.

Linear Search (Sequential Search)

A search algorithm that checks elements one-by-one from the start until the target is found or the collection ends.

Binary Search

A search algorithm for sorted data that repeatedly checks the middle element and discards half of the remaining range each step.

Sorted-Data Precondition

A required condition that the data must be in sorted order (typically ascending) for binary search to work correctly.

low (binary search)

The lower index bound of the current search range in binary search.

high (binary search)

The upper index bound of the current search range in binary search.

mid (binary search)

The middle index of the current range, often computed as (low + high) / 2, used for comparison to the target.

.equals (Java)

A method used to test content/value equality for objects (e.g., Strings) rather than whether they are the same reference.

Reference equality (==)

In Java, for objects, == checks whether two references point to the exact same object, not whether their contents are equal.

Off-by-one Error

A boundary mistake in loop conditions or index updates (e.g., using i <= arr.length), often causing incorrect results or runtime errors.

Sentinel Value (-1)

A conventional return value indicating “not found” when a search method is supposed to return an index.

Sorting

Rearranging elements into a specific order (often ascending or alphabetical), which can enable faster searching and easier data analysis.

Swap (using a temp variable)

A common pattern to exchange two array elements safely by storing one value in a temporary variable first.

Selection Sort

A sorting algorithm that repeatedly finds the smallest remaining element and swaps it into the next position at the front of the array.

minIndex (selection sort)

The index of the smallest value found so far in the unsorted portion during a selection sort pass.

Insertion Sort

A sorting algorithm that builds a sorted prefix by taking the next element (key) and inserting it into the correct position among earlier elements.

key (in insertion sort)

The value being inserted into the already-sorted prefix during an insertion sort iteration.

Shifting (in insertion sort)

Moving larger elements one position to the right to create a “hole” where the key can be inserted.

Comparable

A Java interface for classes that define a natural ordering via a compareTo method (e.g., String implements Comparable).

compareTo

A method that returns a negative number, 0, or a positive number depending on whether an object is less than, equal to, or greater than another in ordering.

Recursion

A technique where a method solves a problem by calling itself on a smaller/simpler input.

Base Case

The stopping condition in a recursive method that does not make another recursive call.

Recursive Case

The part of a recursive method where it calls itself with a smaller input, moving toward the base case.

Divide-and-Conquer

An approach that splits a problem into smaller subproblems, solves them (often recursively), and combines the results.

Merge Sort

A divide-and-conquer sorting algorithm that splits an array into halves, recursively sorts each half, and then merges the sorted halves into a fully sorted array.