M1 Part 2 & 3

Type Parameter

The placeholder for the actual type that will be used, which can be substituted with any concrete type.

Parameterized Type

A generic class or interface that has one or more type parameters.

Bounded Type Parameter

A type parameter with constraints, specifying that the type must be a subclass of a particular class or implement a particular interface.

Generic Method

A method that includes its own type parameters.

Generic Class

A class that can operate on objects of various types while providing compile-time type safety.

Linear Search

A straightforward search algorithm that checks each element in a collection sequentially until the target element is found or the end of the collection is reached.

Equality Comparison

Checking if two elements have the same value, the most common comparison in a linear search.

Identity Comparison

Checking if two elements refer to the exact same object in memory, more stringent than equality.

Abstracted Comparison

Using a generic mechanism for comparison in a linear search that allows it to work with different types of data.

Binary Search

An efficient algorithm for finding a target value within a sorted list by repeatedly dividing the search interval in half.

Sorted List

A list where elements are ordered, either in ascending or descending order, which is a prerequisite for binary search.

Target Value

The value that the binary search algorithm is searching for within the sorted list.

Middle Element

The element located at the midpoint of the current search range, compared to the target value.

Search Range

The portion of the list currently being considered, defined by two indices: the start and end of the range.

Left Half

The segment of the list before the middle element where the search continues if the target value is less than the middle element.

Right Half

The segment of the list after the middle element where the search continues if the target value is greater than the middle element.

Iterative Binary Search

A version of binary search that uses a loop to repeatedly narrow down the search range.

Sorting

The process of arranging elements in a specific order, typically ascending or descending, based on a comparison function.

Ascending

Arranging elements from smallest to largest.

Descending

Arranging elements from largest to smallest.

Stable Sorting

A sorting algorithm is stable if it preserves the relative order of equal elements from the input in the output.

In-Place Sorting

A sorting algorithm is in-place if it requires only a constant amount of extra space aside from the input data.

Comparison-Based Sorting

Sorting algorithms that determine the order of elements by comparing them to one another using a comparison function.

Bubble Sort

A simple comparison-based algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

Selection Sort

A comparison-based algorithm that repeatedly finds the minimum (or maximum) element from the unsorted portion and places it at the beginning (or end) of the list.

Insertion Sort

A comparison-based algorithm that builds the final sorted list one item at a time by repeatedly taking the next element and inserting it into its correct position.

Best Case

The scenario where the algorithm performs the fewest steps.

Worst Case

The scenario where the algorithm performs the most steps.

Average Case

The expected performance across all possible inputs, considered the most practical measure.