Algorithms: Searching, Sorting, and Recursive Methods

Linear Search

A simplest searching algorithm that checks every element in a list sequentially until the target is found.

Binary Search

A faster searching algorithm that divides the search interval in half, requiring a sorted array.

Pre-condition for Binary Search

The array or list MUST be sorted.

Best Case for Linear Search

The target is at the first index, requiring only 1 comparison.

Worst Case for Linear Search

The target is at the last index or not present, requiring N comparisons.

Efficiency of Linear Search

Slower for large lists, operating in O(N) time complexity.

Efficiency of Binary Search

Very fast, operating in O(log N) time complexity.

Selection Sort

An algorithm that finds the minimum element and moves it to its correct place.

Key behavior of Selection Sort

After pass k, the first k elements are sorted and are the k smallest elements.

Insertion Sort

An algorithm that builds a sorted list one element at a time by inserting new elements into their correct positions.

Key behavior of Insertion Sort

After pass k, the first k+1 elements are sorted relative to each other.

Base Case in Recursion

The condition under which the recursion stops and returns a value without calling itself.

Recursive Step

The logic that calls the method again with values closer to the base case.

Merge Sort

A recursive sorting algorithm that uses the Divide and Conquer strategy.

Temporary Array in Merge Sort

Merge Sort requires a helper array to merge elements, using more memory.

Time complexity of Merge Sort

Faster than Selection/Insertion, operating in O(N log N) time.

Call Stack in Recursion

The structure that keeps track of method calls during recursion, allowing the method to pause and resume.

Mistake with Binary Search on Unsorted Data

Trying to trace Binary Search on an unsorted list leads to undefined results.

Off-by-One Error in Binary Search

Mistakenly updating boundaries to low = mid or high = mid instead of moving past mid.

Selection vs. Insertion Sort

Selection Sort swaps elements; Insertion Sort shifts elements.

Infinite Recursion

Occurs when the base case condition is not satisfied, leading to a StackOverflowError.

Factorial Recursive Function

A common recursion example where n! = n × (n-1)!

Divide and Conquer in Merge Sort

The principle where the list is split into halves which are recursively sorted.

Worst Case for Binary Search

Requires log N comparisons when the list is sorted.

Sorting Requirement for Binary Search

The list or array must be sorted to utilize Binary Search effectively.

Conquer phase in Merge Sort

Recursively sort each half of the split list.

Merge step in Merge Sort

Combines two sorted halves into a single sorted list by comparing elements.

Selection Sort Algorithm

Iteratively finds the minimum element and swaps it with the current index.