Detailed Explanation of Search

Algorithms in Java
Linear Search
Definition: Linear Search is a simple search technique that checks each element of the
array sequentially until the desired element is found or the end is reached.

Layman Explanation: Imagine searching for a friend's name in a handwritten list. You go
through each name one by one until you find the correct one.

Time Complexity: Best: O(1), Average/Worst: O(n)

Space Complexity: O(1)

Java Example:
public static int linearSearch(int[] arr, int key) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == key)
return i; // found
}
return -1; // not found
}

Binary Search
Definition: Binary Search is an efficient algorithm that works on sorted arrays by
repeatedly dividing the search interval in half.

Layman Explanation: Think of looking up a word in a dictionary. You open it at the middle
and go left or right depending on the word you're looking for.

Time Complexity: Best: O(1), Average/Worst: O(log n)

Space Complexity: O(1) (Iterative), O(log n) (Recursive)

Java Example:
public static int binarySearch(int[] arr, int key) {
int start = 0, end = arr.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (arr[mid] == key) return mid;
else if (arr[mid] < key) start = mid + 1;
 else end = mid - 1;
}
return -1;
}

Jump Search
Definition: Jump Search is used on sorted arrays and works by jumping ahead by fixed steps
and then performing a linear search in that block.

Layman Explanation: Like skipping 5 pages at a time in a book and then going page by page
once you are close.

Time Complexity: O(√n)

Space Complexity: O(1)

Java Example:
public static int jumpSearch(int[] arr, int key) {
int n = arr.length;
int step = (int)Math.floor(Math.sqrt(n));
int prev = 0;
while (arr[Math.min(step, n) - 1] < key) {
prev = step;
step += (int)Math.floor(Math.sqrt(n));
if (prev >= n) return -1;
}
for (int i = prev; i < Math.min(step, n); i++) {
if (arr[i] == key)
return i;
}
return -1;
}

Interpolation Search
Definition: Interpolation Search improves Binary Search by estimating where the target
might be based on value.

Layman Explanation: Like guessing where a number would be on a ruler based on its size
rather than going straight to the middle.

Time Complexity: Best: O(1), Average: O(log log n), Worst: O(n)

Space Complexity: O(1)

Exponential Search
Definition: Exponential Search first finds a range where the element may exist and then
performs Binary Search in that range.

Layman Explanation: Like doubling steps until you overshoot, then backtrack with Binary
Search.

Time Complexity: O(log n)

Space Complexity: O(1)

Java Example:
public static int exponentialSearch(int[] arr, int key) {
int n = arr.length;
if (arr[0] == key) return 0;
int i = 1;
while (i < n && arr[i] <= key) i *= 2;
return binarySearchInRange(arr, i / 2, Math.min(i, n - 1), key);
}
private static int binarySearchInRange(int[] arr, int low, int high, int key) {
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key) return mid;
else if (arr[mid] < key) low = mid + 1;
else high = mid - 1;
}
return -1;
}
Ternary Search
Definition: Ternary Search divides the search space into three parts instead of two like in
Binary Search.

Layman Explanation: Instead of cutting the list in half, you cut it in three parts and check
two midpoints.

Time Complexity: O(log n)

Space Complexity: O(log n) (recursive)

Java Example:
public static int ternarySearch(int[] arr, int key, int left, int right) {
if (left <= right) {
int mid1 = left + (right - left) / 3;
int mid2 = right - (right - left) / 3;
if (arr[mid1] == key) return mid1;
if (arr[mid2] == key) return mid2;
if (key < arr[mid1]) return ternarySearch(arr, key, left, mid1 - 1);
else if (key > arr[mid2]) return ternarySearch(arr, key, mid2 + 1, right);
else return ternarySearch(arr, key, mid1 + 1, mid2 - 1);
}
return -1;
}
Sorting Algorithms in Java – Definitions,
Examples, and Complexities
Bubble Sort
Definition: Bubble Sort is a simple sorting technique where adjacent elements are compared
and swapped if they are in the wrong order. This process is repeated until the array is
sorted.

Layman Explanation: Imagine bubbling the largest number to the end like bubbles rising in
water.

Time Complexity: Best: O(n) | Average/Worst: O(n²)

Space Complexity: O(1)

Java Example:
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

Selection Sort
Definition: Selection Sort works by repeatedly finding the minimum element and moving it
to the beginning.

Layman Explanation: Like finding the smallest card and placing it in the correct position
repeatedly.

Time Complexity: Best/Average/Worst: O(n²)

Space Complexity: O(1)

Java Example:
public static void selectionSort(int[] arr) {
 for (int i = 0; i < arr.length - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
int temp = arr[minIdx];
arr[minIdx] = arr[i];
arr[i] = temp;
}
}

Insertion Sort
Definition: Insertion Sort builds the final sorted array one item at a time, inserting each new
element into its proper place.

Layman Explanation: Like sorting playing cards in your hand, inserting each in the right
spot.

Time Complexity: Best: O(n) | Average/Worst: O(n²)

Space Complexity: O(1)

Java Example:
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}

Merge Sort
Definition: Merge Sort is a divide-and-conquer algorithm that divides the array, sorts each
half, and merges them.

Layman Explanation: Divide the array into halves, sort them, and then stitch them back
together in order.
Time Complexity: Best/Average/Worst: O(n log n)

Space Complexity: O(n)

Java Example:
public static void mergeSort(int[] arr, int l, int r) {
if (l < r) {
int m = (l + r) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
public static void merge(int[] arr, int l, int m, int r) {
int[] left = Arrays.copyOfRange(arr, l, m + 1);
int[] right = Arrays.copyOfRange(arr, m + 1, r + 1);
int i = 0, j = 0, k = l;
while (i < left.length && j < right.length) {
arr[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
}
while (i < left.length) arr[k++] = left[i++];
while (j < right.length) arr[k++] = right[j++];
}

Quick Sort
Definition: Quick Sort is a divide-and-conquer algorithm that picks a pivot and partitions
the array into elements less than and greater than the pivot.

Layman Explanation: Pick a number (pivot), put smaller ones to the left, bigger to the right,
then repeat.

Time Complexity: Best/Average: O(n log n) | Worst: O(n²)

Space Complexity: O(log n) (recursive)

Java Example:
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
public static int partition(int[] arr, int low, int high) {
 int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}

Heap Sort
Definition: Heap Sort builds a binary heap from the array and repeatedly extracts the max
element to sort the array.

Layman Explanation: Turn the array into a tree where the biggest number is at the top, then
remove and repeat.

Time Complexity: Best/Average/Worst: O(n log n)

Space Complexity: O(1)

Java Example:
public static void heapSort(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
public static void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
 if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}