Searching and Sorting Algorithms

A Complete Technical Reference Guide

with Java Implementations, Verified Output,
and Complexity Analysis

Compiled and verified using OpenJDK 21 (JDK for Windows compatible)

July 2026
Table of Contents

Part I — Sorting Algorithms

1.1 Bubble Sort

1.2 Selection Sort

1.3 Insertion Sort

1.4 Merge Sort

1.5 Quick Sort

1.6 Heap Sort

1.7 Shell Sort

1.8 Counting Sort

1.9 Radix Sort

1.10 Bucket Sort

Part II — Searching Algorithms

2.1 Linear Search

2.2 Binary Search

2.3 Jump Search

2.4 Interpolation Search

2.5 Exponential Search

2.6 Ternary Search

2.7 Fibonacci Search
 Part I

Sorting Algorithms
 1.1 Bubble Sort

IN SIMPLE WORDS
Imagine people standing in a line, and you compare each pair of neighbours, swapping them if the one in front is bigger than the one behind.
Repeat this walk down the line again and again — the biggest values slowly "bubble" to the end.

Description

Bubble Sort repeatedly steps through the array, compares each pair of adjacent elements, and swaps them if they are in the wrong order.
The largest unsorted element "bubbles up" to its correct position on every pass.

Step-by-step working:
1. Start at the beginning of the array.
2. Compare each pair of adjacent elements.
3. If the left element is greater than the right one, swap them.
4. Continue to the end of the array — this completes one pass, placing the largest element at the end.
5. Repeat the passes for the remaining unsorted portion of the array.
6. Stop early if a full pass completes with no swaps — the array is already sorted.

Java Implementation

public class BubbleSort {

static void bubbleSort(int[] arr) {

int n = [Link];
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break;
}
}

static void printArray(int[] arr) {

for (int val : arr) [Link](val + " ");
[Link]();
}

public static void main(String[] args) {

int[] arr = {64, 34, 25, 12, 22, 11, 90};
[Link]("Original array: ");
printArray(arr);

bubbleSort(arr);

[Link]("Sorted array: ");

printArray(arr);
}
}

Program Output

Original array: 64 34 25 12 22 11 90
Sorted array: 11 12 22 25 34 64 90

Time & Space Complexity Analysis

Best Case O(n) Average Case O(n^2)

Worst Case O(n^2) Space Complexity O(1)

Stable Yes In-Place Yes

Why is it like this?

Every element is compared with its neighbour across up to (n-1) passes, and each pass re-checks almost the whole remaining list, giving roughly n +
(n-1) + (n-2) + ... + 1 comparisons — which adds up to about n²/2, so we say O(n²). If the data is already sorted, one single pass with no swaps is
enough to confirm it, so the best case drops to O(n). No extra memory is used besides one swap variable, so space stays O(1).

Note: The best case occurs on an already-sorted array because of the swap flag that allows early termination.
 1.2 Selection Sort

IN SIMPLE WORDS
Imagine you keep picking out the smallest remaining item from a messy pile and placing it into a new, growing line — one item at a time, always
taking the smallest one left in the pile.

Description

Selection Sort divides the array into a sorted and an unsorted region. On every iteration it selects the smallest element from the unsorted
region and moves it to the end of the sorted region.

Step-by-step working:
1. Set the first element as the current minimum position.
2. Scan the remaining unsorted elements to find the smallest value.
3. Swap the smallest value found with the element at the current minimum position.
4. Move the boundary between sorted and unsorted regions one step forward.
5. Repeat until the entire array is sorted.

Java Implementation

public class SelectionSort {

static void selectionSort(int[] arr) {

int n = [Link];
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}

static void printArray(int[] arr) {

for (int val : arr) [Link](val + " ");
[Link]();
}

public static void main(String[] args) {

int[] arr = {64, 25, 12, 22, 11};
[Link]("Original array: ");
printArray(arr);

selectionSort(arr);

[Link]("Sorted array: ");

printArray(arr);
}
}

Program Output

Original array: 64 25 12 22 11
Sorted array: 11 12 22 25 64

Time & Space Complexity Analysis

Best Case O(n^2) Average Case O(n^2)

Worst Case O(n^2) Space Complexity O(1)

Stable No In-Place Yes

Why is it like this?

To place just one element correctly, the algorithm must scan every remaining unsorted item to find the smallest one — it cannot skip this scan even
if the data is already sorted. Doing this scan n times (once per position) gives about n + (n-1) + ... + 1 comparisons, which is roughly n², so best,
average, and worst case are all O(n²). Swapping happens directly inside the same array, so space stays O(1).

Note: Selection Sort always performs the same number of comparisons regardless of input order, so its best and worst cases are identical.
 1.3 Insertion Sort

IN SIMPLE WORDS
Just like sorting playing cards in your hand — you pick up one card at a time from the table and slide it into its correct place among the cards you
are already holding in order.

Description

Insertion Sort builds the final sorted array one element at a time. It takes each new element and inserts it into its correct position among
the already-sorted elements to its left, similar to how a person sorts playing cards in hand.

Step-by-step working:
1. Consider the first element to already be a sorted sub-array of size one.
2. Pick the next element as the "key".
3. Compare the key with elements in the sorted sub-array from right to left.
4. Shift every element greater than the key one position to the right.
5. Insert the key into the resulting gap.
6. Repeat for all remaining elements in the array.

Java Implementation

public class InsertionSort {

static void insertionSort(int[] arr) {

int n = [Link];
for (int i = 1; i < n; 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;
}
}

static void printArray(int[] arr) {

for (int val : arr) [Link](val + " ");
[Link]();
}

public static void main(String[] args) {

int[] arr = {12, 11, 13, 5, 6};
[Link]("Original array: ");
printArray(arr);

insertionSort(arr);

[Link]("Sorted array: ");

printArray(arr);
}
}

Program Output

Original array: 12 11 13 5 6
Sorted array: 5 6 11 12 13

Time & Space Complexity Analysis

Best Case O(n) Average Case O(n^2)

Worst Case O(n^2) Space Complexity O(1)

Stable Yes In-Place Yes

Why is it like this?

If the array is already sorted, each new element only needs one comparison to confirm it is already in place, giving O(n) overall. But if the array is in
reverse order, every new element must shift past all the previously-sorted elements, leading to about 1 + 2 + ... + (n-1) shifts, which is roughly n², so
the worst and average case are O(n²). Elements are shifted within the same array, so space usage stays O(1).

Note: Very efficient for small or nearly-sorted datasets; the best case occurs when the input is already sorted.
 1.4 Merge Sort

IN SIMPLE WORDS
Like splitting a deck of cards in half again and again until each pile has only one card, and then repeatedly combining piles back together in the
correct order until the full deck is sorted.

Description

Merge Sort is a divide-and-conquer algorithm. It recursively splits the array into halves until each piece has one element, then merges the
pieces back together in sorted order.

Step-by-step working:
1. If the array has more than one element, find the middle point to divide it into two halves.
2. Recursively call Merge Sort on the left half.
3. Recursively call Merge Sort on the right half.
4. Merge the two sorted halves back into a single sorted sequence by repeatedly picking the smaller of the two front elements.
5. Copy any remaining elements from either half once the other is exhausted.

Java Implementation

public class MergeSort {

static void mergeSort(int[] arr, int left, int right) {

if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}

static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;

int[] leftArr = new int[n1];

int[] rightArr = new int[n2];

[Link](arr, left, leftArr, 0, n1);

[Link](arr, mid + 1, rightArr, 0, n2);

int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
while (i < n1) arr[k++] = leftArr[i++];
while (j < n2) arr[k++] = rightArr[j++];
}

static void printArray(int[] arr) {

for (int val : arr) [Link](val + " ");
[Link]();
}

public static void main(String[] args) {

int[] arr = {38, 27, 43, 3, 9, 82, 10};
[Link]("Original array: ");
printArray(arr);

mergeSort(arr, 0, [Link] - 1);

[Link]("Sorted array: ");

printArray(arr);
}
}

Program Output

Original array: 38 27 43 3 9 82 10
Sorted array: 3 9 10 27 38 43 82

Time & Space Complexity Analysis

Best Case O(n log n) Average Case O(n log n)

Worst Case O(n log n) Space Complexity O(n)

 Stable Yes In-Place No

Why is it like this?

Splitting the array in half every time always creates log n levels of division, no matter how the data is arranged. At every level, merging all the pieces
back together touches every element once, costing O(n) per level. Multiplying the levels by the per-level cost gives O(n log n) in every case. The
merge step needs a temporary array to hold elements while combining, which is why the space cost is O(n).

Note: Guarantees O(n log n) performance in every case, which makes it a reliable choice for large datasets, at the cost of extra memory for the merge step.
 1.5 Quick Sort

IN SIMPLE WORDS
Pick one person as a reference point, then ask everyone shorter to stand on one side and everyone taller to stand on the other side. Repeat this
same trick separately within each side until everyone is in order.

Description

Quick Sort is a divide-and-conquer algorithm that picks a "pivot" element and partitions the array so that smaller elements land to its left
and larger elements to its right, then recursively sorts each partition.

Step-by-step working:
1. Choose a pivot element (this implementation uses the last element of the range).
2. Partition the array: move all elements smaller than the pivot before it, and all larger elements after it.
3. The pivot is now in its final sorted position.
4. Recursively apply the same process to the sub-array on the left of the pivot.
5. Recursively apply the same process to the sub-array on the right of the pivot.

Java Implementation

public class QuickSort {

static void quickSort(int[] arr, int low, int high) {

if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}

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;
}

static void printArray(int[] arr) {

for (int val : arr) [Link](val + " ");
[Link]();
}

public static void main(String[] args) {

int[] arr = {10, 7, 8, 9, 1, 5};
[Link]("Original array: ");
printArray(arr);

quickSort(arr, 0, [Link] - 1);

[Link]("Sorted array: ");

printArray(arr);
}
}

Program Output

Original array: 10 7 8 9 1 5
Sorted array: 1 5 7 8 9 10

Time & Space Complexity Analysis

Best Case O(n log n) Average Case O(n log n)

Worst Case O(n^2) Space Complexity O(log n)

Stable No In-Place Yes

Why is it like this?

When the pivot happens to split the array into two roughly equal halves each time, there are about log n levels of splitting, and each level does O(n)
work to partition — giving O(n log n). But if the pivot is always the smallest or largest value (as can happen with sorted input), each split only
removes one element, creating n levels instead of log n, which multiplies out to O(n²). The recursive calls use the call stack, which needs O(log n)
space in the balanced case.

Note: The worst case (O(n^2)) happens on already-sorted or reverse-sorted input with a poor pivot choice; randomized or median-of-three pivot selection
reduces this risk in practice.
 1.6 Heap Sort

IN SIMPLE WORDS
Picture a group of people arranged so the tallest is always at the front. Keep pulling out the tallest person, place them at the end of the final line,
and rearrange what's left so the next tallest again comes to the front.

Description

Heap Sort first transforms the array into a max-heap, a binary tree structure where every parent node is greater than or equal to its
children. It then repeatedly removes the largest element (the root) and rebuilds the heap.

Step-by-step working:
1. Build a max-heap from the input array.
2. Swap the root of the heap (the largest element) with the last element of the array.
3. Reduce the heap size by one, excluding the now-sorted last element.
4. "Heapify" the root to restore the max-heap property.
5. Repeat the swap-and-heapify steps until the heap size is one.

Java Implementation

public class HeapSort {

static void heapSort(int[] arr) {

int n = [Link];

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);
}
}

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);
}
}

static void printArray(int[] arr) {

for (int val : arr) [Link](val + " ");
[Link]();
}

public static void main(String[] args) {

int[] arr = {12, 11, 13, 5, 6, 7};
[Link]("Original array: ");
printArray(arr);

heapSort(arr);

[Link]("Sorted array: ");

printArray(arr);
}
}

Program Output

Original array: 12 11 13 5 6 7
Sorted array: 5 6 7 11 12 13

Time & Space Complexity Analysis

Best Case O(n log n) Average Case O(n log n)

Worst Case O(n log n) Space Complexity O(1)

 Stable No In-Place Yes

Why is it like this?

Building the initial heap costs O(n), and then the largest element is removed one at a time — n times in total. Restoring the heap shape after each
removal (called "heapify") takes O(log n) because the heap is a balanced binary tree. Multiplying n removals by O(log n) each gives O(n log n), and
this holds regardless of the original order of the data. Because the heap is stored inside the same array, no extra array is needed, so space is O(1).

Note: Consistently guarantees O(n log n) time with only constant extra space, making it attractive when memory is limited.
 1.7 Shell Sort

IN SIMPLE WORDS
Like Insertion Sort, but instead of only comparing neighbours, you first compare people standing far apart, gradually bringing them closer
together in later rounds — fixing big mistakes early so later steps have less work to do.

Description

Shell Sort is a generalisation of Insertion Sort that first compares elements far apart from each other (using a "gap") and progressively
reduces the gap, allowing elements to move faster toward their correct position.

Step-by-step working:
1. Choose an initial gap value, typically n / 2.
2. Compare elements that are 'gap' positions apart and perform an insertion-sort-style shift for each such pair.
3. Reduce the gap (this implementation halves it each round).
4. Repeat the gapped insertion sort with the smaller gap.
5. Continue until the gap becomes 1, which performs a final, now nearly-effortless, standard insertion sort.

Java Implementation

public class ShellSort {

static void shellSort(int[] arr) {

int n = [Link];
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}

static void printArray(int[] arr) {

for (int val : arr) [Link](val + " ");
[Link]();
}

public static void main(String[] args) {

int[] arr = {23, 29, 15, 19, 31, 7, 9, 5, 2};
[Link]("Original array: ");
printArray(arr);

shellSort(arr);

[Link]("Sorted array: ");

printArray(arr);
}
}

Program Output

Original array: 23 29 15 19 31 7 9 5 2
Sorted array: 2 5 7 9 15 19 23 29 31

Time & Space Complexity Analysis

Best Case O(n log n) Average Case O(n^1.3) (gap-sequence dependent)

Worst Case O(n^2) Space Complexity O(1)

Stable No In-Place Yes

Why is it like this?

Comparing far-apart elements first moves badly-placed values closer to their correct spot much faster than plain Insertion Sort would. Because each
round with a smaller gap has less work left to do, the total work adds up to less than n², though the exact figure depends on the sequence of gaps
chosen — for the halving sequence used here it is roughly O(n^1.3) on average. In the rare worst case the gaps do not help much and it falls back
toward O(n²). No extra array is used, so space is O(1).

Note: Performance depends heavily on the chosen gap sequence; the classic n/2 halving sequence used here gives good practical performance, though
better sequences (e.g. Knuth's) can push the average case lower.
 1.8 Counting Sort

IN SIMPLE WORDS
Like counting how many students scored each mark in a class test, and then listing the students out from the lowest mark to the highest based
purely on those counts — without ever comparing two students directly.

Description

Counting Sort is a non-comparison sort that works by counting how many times each distinct value appears, then using those counts to
place every element directly into its final sorted position.

Step-by-step working:
1. Find the minimum and maximum values in the array to determine the value range.
2. Create a count array sized to that range and tally the occurrences of every value.
3. Transform the count array into a running total (prefix sum) so each cell holds the position where that value's block ends.
4. Walk the original array from right to left, placing each element into the output array at the position given by the prefix sums,
decrementing the count as you go.
5. Copy the output array back over the original array.

Java Implementation

public class CountingSort {

static void countingSort(int[] arr) {

int n = [Link];
if (n == 0) return;

int max = arr[0], min = arr[0];

for (int val : arr) {
if (val > max) max = val;
if (val < min) min = val;
}

int range = max - min + 1;

int[] count = new int[range];
int[] output = new int[n];

for (int val : arr) count[val - min]++;

for (int i = 1; i < range; i++) count[i] += count[i - 1];

for (int i = n - 1; i >= 0; i--) {

output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}

[Link](output, 0, arr, 0, n);

}

static void printArray(int[] arr) {

for (int val : arr) [Link](val + " ");
[Link]();
}

public static void main(String[] args) {

int[] arr = {4, 2, 2, 8, 3, 3, 1};
[Link]("Original array: ");
printArray(arr);

countingSort(arr);

[Link]("Sorted array: ");

printArray(arr);
}
}

Program Output

Original array: 4 2 2 8 3 3 1
Sorted array: 1 2 2 3 3 4 8

Time & Space Complexity Analysis

Best Case O(n + k) Average Case O(n + k)

Worst Case O(n + k) Space Complexity O(n + k)

Stable Yes In-Place No

Why is it like this?

Instead of comparing elements, the algorithm just counts how many times each value appears — this takes one pass through the n elements, O(n). It
then builds a running total across the k possible values, O(k), and does one more pass to place every element into its final position, O(n). Adding
these steps gives O(n + k), and this never changes no matter how the input is ordered. The count array and output array both need extra memory,
giving O(n + k) space.

Note: Here k is the range of input values. Extremely fast when k is comparable to n, but memory and time both grow with the value range, so it is unsuitable
for widely-spread values.
 1.9 Radix Sort

IN SIMPLE WORDS
Like sorting a stack of mail by postal code — first arranging by the last digit, then by the second-last digit, and so on, until the leftmost digit has
been used, leaving the whole stack fully sorted.

Description

Radix Sort sorts integers digit by digit, from the least significant digit to the most significant, using a stable sort (Counting Sort) as a
subroutine at each digit position.

Step-by-step working:
1. Find the maximum value in the array to determine the number of digits to process.
2. Starting with the least significant digit (units place), sort the entire array using a stable counting sort based on that digit.
3. Move to the next digit (tens, then hundreds, and so on) and repeat the stable sort.
4. Continue until every digit position up to the maximum number of digits has been processed.
5. The array is fully sorted once the most significant digit has been processed.

Java Implementation

public class RadixSort {

static void radixSort(int[] arr) {

int max = getMax(arr);
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSortByDigit(arr, exp);
}
}

static int getMax(int[] arr) {

int max = arr[0];
for (int val : arr) if (val > max) max = val;
return max;
}

static void countingSortByDigit(int[] arr, int exp) {

int n = [Link];
int[] output = new int[n];
int[] count = new int[10];

for (int i = 0; i < n; i++) count[(arr[i] / exp) % 10]++;

for (int i = 1; i < 10; i++) count[i] += count[i - 1];

for (int i = n - 1; i >= 0; i--) {

int digit = (arr[i] / exp) % 10;
output[count[digit] - 1] = arr[i];
count[digit]--;
}

[Link](output, 0, arr, 0, n);

}

static void printArray(int[] arr) {

for (int val : arr) [Link](val + " ");
[Link]();
}

public static void main(String[] args) {

int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
[Link]("Original array: ");
printArray(arr);

radixSort(arr);

[Link]("Sorted array: ");

printArray(arr);
}
}

Program Output

Original array: 170 45 75 90 802 24 2 66

Sorted array: 2 24 45 66 75 90 170 802

Time & Space Complexity Analysis

Best Case O(d * (n + b)) Average Case O(d * (n + b))

Worst Case O(d * (n + b)) Space Complexity O(n + b)

 Stable Yes In-Place No

Why is it like this?

The algorithm runs one counting-sort pass for every digit position, and each of those passes costs O(n + b), where b is the number of possible digit
values (10 for base ten). Running this for all d digit positions gives O(d × (n + b)) in total, and this cost is fixed by the size of the numbers, not their
order — so it stays the same in every case. Each pass needs its own count and output arrays, giving O(n + b) space.

Note: Here d is the number of digits in the largest number and b is the base (10 in this implementation). Because d is typically small and constant, Radix Sort
behaves close to linear time for fixed-width integers.
 1.10 Bucket Sort

IN SIMPLE WORDS
Like sorting fruit by size into separate baskets first, then quickly arranging the few pieces inside each basket, and finally lining up the baskets in
order — much less work than sorting everything together at once.

Description

Bucket Sort distributes elements into a number of "buckets" based on their value, sorts each bucket individually (typically with a simple
sort), and then concatenates the buckets in order. It works best on uniformly distributed floating-point data in a known range.

Step-by-step working:
1. Create an empty bucket for each element in the input (n buckets).
2. For every element, compute a bucket index based on its value and place the element into that bucket.
3. Sort the contents of each individual bucket (this implementation uses [Link] on each bucket's list).
4. Concatenate all the buckets in order to produce the final sorted array.

Java Implementation

import [Link];
import [Link];
import [Link];

public class BucketSort {

static void bucketSort(double[] arr) {

int n = [Link];
if (n <= 0) return;

List<List<Double>> buckets = new ArrayList<>();

for (int i = 0; i < n; i++) [Link](new ArrayList<>());

for (double val : arr) {

int bucketIndex = (int) (val * n);
[Link](bucketIndex).add(val);
}

for (List<Double> bucket : buckets) {

[Link](bucket);
}

int index = 0;
for (List<Double> bucket : buckets) {
for (double val : bucket) {
arr[index++] = val;
}
}
}

static void printArray(double[] arr) {

for (double val : arr) [Link](val + " ");
[Link]();
}

public static void main(String[] args) {

double[] arr = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};
[Link]("Original array: ");
printArray(arr);

bucketSort(arr);

[Link]("Sorted array: ");

printArray(arr);
}
}

Program Output

Original array: 0.897 0.565 0.656 0.1234 0.665 0.3434

Sorted array: 0.1234 0.3434 0.565 0.656 0.665 0.897

Time & Space Complexity Analysis

Best Case O(n + k) Average Case O(n + k)

Worst Case O(n^2) Space Complexity O(n + k)

Stable Yes In-Place No

Why is it like this?

Placing all n elements into their buckets takes O(n). If the data is spread evenly, each of the k buckets ends up with only a handful of elements, so
sorting all buckets together costs roughly O(n + k). But if the data is uneven and everything lands in one bucket, sorting that single overloaded
bucket becomes as slow as an O(n²) sort. Extra memory is needed to hold the buckets themselves, giving O(n + k) space.

Note: k is the number of buckets. The worst case occurs when all elements land in a single bucket; performance depends on how uniformly the input is
distributed.
 Part II

Searching Algorithms
 2.1 Linear Search

IN SIMPLE WORDS
Like scanning a shopping list from top to bottom to check if an item is on it — you check every single line, one after another, until you find it.

Description

Linear Search examines every element of the array one by one, in order, until it finds the target value or reaches the end of the array. It
requires no particular ordering of the data.

Step-by-step working:
1. Start from the first element of the array.
2. Compare the current element with the target value.
3. If they match, return the current index.
4. Otherwise, move to the next element.
5. If the end of the array is reached with no match, report that the element was not found.

Java Implementation

public class LinearSearch {

static int linearSearch(int[] arr, int target) {

for (int i = 0; i < [Link]; i++) {
if (arr[i] == target) return i;
}
return -1;
}

public static void main(String[] args) {

int[] arr = {45, 12, 78, 34, 90, 23, 56};
int target = 34;

[Link]("Array: {45, 12, 78, 34, 90, 23, 56}");

[Link]("Target: " + target);

int result = linearSearch(arr, target);

if (result != -1) {
[Link]("Element found at index: " + result);
} else {
[Link]("Element not found in the array.");
}
}
}

Program Output

Array: {45, 12, 78, 34, 90, 23, 56}

Target: 34
Element found at index: 3

Time & Space Complexity Analysis

Best Case O(1) Average Case O(n)

Worst Case O(n) Space Complexity O(1)

Why is it like this?

If the target happens to be the very first element checked, only one comparison is needed, giving the best case O(1). But if the target is at the very
end, or missing altogether, every single one of the n elements must be checked, giving O(n) for the average and worst case. Since only one index
variable is used to track position, no extra memory grows with input size, so space is O(1).

Note: Works on unsorted data, but is inefficient for large datasets compared to search algorithms that exploit sorted order.
 2.2 Binary Search

IN SIMPLE WORDS
Like looking up a word in a printed dictionary — you open it in the middle, see if your word comes before or after that page, and keep repeating
this halving trick until you land on the word.

Description

Binary Search operates on a sorted array. It repeatedly divides the search range in half, comparing the target with the middle element and
discarding the half of the array that cannot contain the target.

Step-by-step working:
1. Set low and high pointers to the start and end of the array.
2. Compute the middle index of the current range.
3. If the middle element equals the target, return its index.
4. If the target is greater than the middle element, discard the left half and search only the right half.
5. If the target is smaller, discard the right half and search only the left half.
6. Repeat until the element is found or the range becomes empty.

Java Implementation

public class BinarySearch {

static int binarySearch(int[] arr, int target) {

int low = 0, high = [Link] - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}

public static void main(String[] args) {

int[] arr = {11, 23, 34, 45, 56, 67, 78, 90};
int target = 56;

[Link]("Sorted array: {11, 23, 34, 45, 56, 67, 78, 90}");
[Link]("Target: " + target);

int result = binarySearch(arr, target);

if (result != -1) {
[Link]("Element found at index: " + result);
} else {
[Link]("Element not found in the array.");
}
}
}

Program Output

Sorted array: {11, 23, 34, 45, 56, 67, 78, 90}
Target: 56
Element found at index: 4

Time & Space Complexity Analysis

Best Case O(1) Average Case O(log n)

Worst Case O(log n) Space Complexity O(1)

Why is it like this?

Every comparison throws away half of the remaining elements, so the search space shrinks from n, to n/2, to n/4, and so on. The number of times n
can be halved before only one element is left is log₂(n), which is why the time complexity is O(log n). If the very first middle element checked
happens to match, the best case is just O(1). Because this implementation only tracks two pointers (low and high) instead of creating new arrays, the
space stays O(1).

Note: Requires the array to be sorted beforehand. The iterative version used here keeps space usage constant, unlike a recursive implementation.
 2.3 Jump Search

IN SIMPLE WORDS
Like flipping through a sorted phonebook in fixed jumps of a few pages at a time until you land near the name you want, and then reading page
by page from there.

Description

Jump Search works on sorted arrays by jumping ahead in fixed-size blocks to find the block that could contain the target, then performing
a linear scan within that block.

Step-by-step working:
1. Choose a block (jump) size, typically the square root of the array length.
2. Jump forward block by block until finding a block whose last element is greater than or equal to the target.
3. Perform a linear search within that block, starting from its first element.
4. If the target is found, return its index; otherwise report it is absent.

Java Implementation

public class JumpSearch {

static int jumpSearch(int[] arr, int target) {

int n = [Link];
int step = (int) [Link]([Link](n));
int prev = 0;

while (arr[[Link](step, n) - 1] < target) {

prev = step;
step += (int) [Link]([Link](n));
if (prev >= n) return -1;
}

while (arr[prev] < target) {

prev++;
if (prev == [Link](step, n)) return -1;
}

if (arr[prev] == target) return prev;

return -1;
}

public static void main(String[] args) {

int[] arr = {2, 4, 8, 12, 17, 23, 29, 35, 42, 50, 61, 72};
int target = 42;

[Link]("Sorted array: {2, 4, 8, 12, 17, 23, 29, 35, 42, 50, 61, 72}");
[Link]("Target: " + target);

int result = jumpSearch(arr, target);

if (result != -1) {
[Link]("Element found at index: " + result);
} else {
[Link]("Element not found in the array.");
}
}
}

Program Output

Sorted array: {2, 4, 8, 12, 17, 23, 29, 35, 42, 50, 61, 72}
Target: 42
Element found at index: 8

Time & Space Complexity Analysis

Best Case O(1) Average Case O(sqrt(n))

Worst Case O(sqrt(n)) Space Complexity O(1)

Why is it like this?

The total work is the number of jumps (n divided by the block size) plus the final linear scan inside one block (the block size itself). Adding n/block +
block and choosing the block size that minimises this sum through basic calculus gives block = √n, which makes the total work about 2√n — so the
complexity is written as O(√n). Only a couple of index variables are tracked, so space is O(1).

Note: A middle ground between Linear Search and Binary Search — faster than linear scanning while being simpler to reason about than repeated halving.
 2.4 Interpolation Search

IN SIMPLE WORDS
Like opening a dictionary near the back if you are looking for a word starting with "Y", instead of always opening it exactly in the middle — you
guess a smarter starting point based on the value itself.

Description

Interpolation Search improves on Binary Search for uniformly distributed sorted data. Instead of always checking the middle element, it
estimates the likely position of the target using linear interpolation, similar to how a person looks up a name in a phone book.

Step-by-step working:
1. Confirm the target lies within the value range of the current low and high bounds.
2. Estimate the probable position of the target using the proportion of its value between the low and high values.
3. Compare the element at the estimated position with the target.
4. If it matches, return the index; otherwise narrow the search range above or below the estimated position, similar to Binary Search.
5. Repeat until the target is found or the range is exhausted.

Java Implementation

public class InterpolationSearch {

static int interpolationSearch(int[] arr, int target) {

int low = 0, high = [Link] - 1;

while (low <= high && target >= arr[low] && target <= arr[high]) {
if (low == high) {
if (arr[low] == target) return low;
return -1;
}

int pos = low + (int) (((long) (high - low) * (target - arr[low])) / (arr[high] - arr[low]));

if (arr[pos] == target) return pos;

else if (arr[pos] < target) low = pos + 1;
else high = pos - 1;
}
return -1;
}

public static void main(String[] args) {

int[] arr = {10, 20, 25, 35, 42, 55, 63, 78, 84, 91};
int target = 63;

[Link]("Sorted array: {10, 20, 25, 35, 42, 55, 63, 78, 84, 91}");
[Link]("Target: " + target);

int result = interpolationSearch(arr, target);

if (result != -1) {
[Link]("Element found at index: " + result);
} else {
[Link]("Element not found in the array.");
}
}
}

Program Output

Sorted array: {10, 20, 25, 35, 42, 55, 63, 78, 84, 91}
Target: 63
Element found at index: 6

Time & Space Complexity Analysis

Best Case O(1) Average Case O(log log n)

Worst Case O(n) Space Complexity O(1)

Why is it like this?

When values are spread out evenly, the estimated position is usually very close to the target's true position, so the search range shrinks much faster
than simple halving — mathematically this works out to about O(log log n) on average. But if the values are bunched unevenly, the estimate can be
badly wrong every time, causing the range to shrink by only one element per step, which degrades to O(n) in the worst case. Only a few pointers are
tracked, so space stays O(1).

Note: Performs best on uniformly distributed data. Its worst case degrades to linear time when the data is very unevenly distributed.
 2.5 Exponential Search

IN SIMPLE WORDS
Like taking bigger and bigger steps forward — 1, then 2, then 4, then 8 pages at a time — until you jump past where your target should be, then
carefully searching back within that last small range.

Description

Exponential Search finds a range in which the target may lie by repeatedly doubling an index, then performs a Binary Search within that
bounded range. It is especially useful for unbounded or very large sorted arrays.

Step-by-step working:
1. Check if the target is the first element; if so, return index 0.
2. Starting from index 1, repeatedly double the index while the element at that index is less than or equal to the target.
3. Once the doubling overshoots the target (or the array end), a valid range has been identified between the previous and current index.
4. Run Binary Search within that bounded range to locate the exact position of the target.

Java Implementation

public class ExponentialSearch {

static int binarySearch(int[] arr, int low, int high, int target) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}

static int exponentialSearch(int[] arr, int target) {

int n = [Link];
if (arr[0] == target) return 0;

int i = 1;
while (i < n && arr[i] <= target) {
i *= 2;
}

return binarySearch(arr, i / 2, [Link](i, n - 1), target);

}

public static void main(String[] args) {

int[] arr = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91};
int target = 45;

[Link]("Sorted array: {2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91}");
[Link]("Target: " + target);

int result = exponentialSearch(arr, target);

if (result != -1) {
[Link]("Element found at index: " + result);
} else {
[Link]("Element not found in the array.");
}
}
}

Program Output

Sorted array: {2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91}
Target: 45
Element found at index: 7

Time & Space Complexity Analysis

Best Case O(1) Average Case O(log n)

Worst Case O(log n) Space Complexity O(1)

Why is it like this?

Doubling the index (1, 2, 4, 8, ...) to find the range containing the target takes only about log₂(n) doubling steps, since the index grows so quickly.
The Binary Search that follows within that small range then takes another O(log n) steps. Adding two O(log n) stages together is still O(log n) overall,
just with a slightly larger constant. Space stays O(1) since no extra arrays are created.

Note: Particularly effective when the target is near the beginning of the array, or when the array size is unknown in advance.
 2.6 Ternary Search

IN SIMPLE WORDS
Similar to Binary Search, but instead of splitting the list into two parts, you split it into three parts and check two marker points to decide which
third to continue searching in.

Description

Ternary Search operates on a sorted array by splitting the current range into three parts using two mid-points, then discarding the third of
the range that cannot contain the target.

Step-by-step working:
1. Compute two mid-points that divide the current range into three roughly equal parts.
2. Compare the target with the elements at both mid-points; return the index immediately on a match.
3. If the target is smaller than the first mid-point's value, search only the first third.
4. If the target is larger than the second mid-point's value, search only the last third.
5. Otherwise, search the middle third.
6. Repeat recursively until the target is found or the range becomes empty.

Java Implementation

public class TernarySearch {

static int ternarySearch(int[] arr, int low, int high, int target) {
if (high >= low) {
int mid1 = low + (high - low) / 3;
int mid2 = high - (high - low) / 3;

if (arr[mid1] == target) return mid1;

if (arr[mid2] == target) return mid2;

if (target < arr[mid1]) {

return ternarySearch(arr, low, mid1 - 1, target);
} else if (target > arr[mid2]) {
return ternarySearch(arr, mid2 + 1, high, target);
} else {
return ternarySearch(arr, mid1 + 1, mid2 - 1, target);
}
}
return -1;
}

public static void main(String[] args) {

int[] arr = {3, 7, 11, 19, 24, 30, 37, 45, 52, 60, 68};
int target = 52;

[Link]("Sorted array: {3, 7, 11, 19, 24, 30, 37, 45, 52, 60, 68}");
[Link]("Target: " + target);

int result = ternarySearch(arr, 0, [Link] - 1, target);

if (result != -1) {
[Link]("Element found at index: " + result);
} else {
[Link]("Element not found in the array.");
}
}
}

Program Output

Sorted array: {3, 7, 11, 19, 24, 30, 37, 45, 52, 60, 68}
Target: 52
Element found at index: 8

Time & Space Complexity Analysis

Best Case O(1) Average Case O(log3 n)

Worst Case O(log3 n) Space Complexity O(log n)

Why is it like this?

Splitting the range into three parts instead of two means the range shrinks using log base 3 instead of log base 2, needing fewer splitting rounds.
However, each round now checks two mid-points instead of one, so the number of comparisons per round is higher. These two effects roughly cancel
out, leaving the growth rate the same order as Binary Search, O(log n), just with a larger constant factor. The recursive calls use the call stack, giving
O(log n) space.
Note: Makes more comparisons per step than Binary Search, so despite a smaller logarithm base it is typically not faster in practice; it is mainly used for
finding extrema in unimodal functions.
 2.7 Fibonacci Search

IN SIMPLE WORDS
Very similar to Binary Search, but instead of always splitting exactly in half, it splits the list using Fibonacci numbers (1, 1, 2, 3, 5, 8, 13...) which
only needs addition and subtraction instead of division.

Description

Fibonacci Search is similar to Binary Search but divides the array using Fibonacci numbers instead of a simple midpoint, which can be
useful in systems where division operations are costly, since it relies only on addition and subtraction.

Step-by-step working:
1. Find the smallest Fibonacci number greater than or equal to the array length.
2. Use the Fibonacci numbers to mark a comparison point within the unexplored range.
3. If the element at that point is less than the target, shift the range forward and reduce to the next-smaller pair of Fibonacci numbers.
4. If it is greater than the target, reduce the range from the other side using a smaller pair of Fibonacci numbers.
5. If it matches the target, return the index.
6. Repeat until the Fibonacci numbers are reduced to a trivial case, then check any single remaining element.

Java Implementation

public class FibonacciSearch {

static int fibonacciSearch(int[] arr, int target) {

int n = [Link];

int fib2 = 0;
int fib1 = 1;
int fib = fib1 + fib2;

while (fib < n) {

fib2 = fib1;
fib1 = fib;
fib = fib1 + fib2;
}

int offset = -1;

while (fib > 1) {

int i = [Link](offset + fib2, n - 1);

if (arr[i] < target) {

fib = fib1;
fib1 = fib2;
fib2 = fib - fib1;
offset = i;
} else if (arr[i] > target) {
fib = fib2;
fib1 = fib1 - fib2;
fib2 = fib - fib1;
} else {
return i;
}
}

if (fib1 == 1 && offset + 1 < n && arr[offset + 1] == target) {

return offset + 1;
}

return -1;
}

public static void main(String[] args) {

int[] arr = {10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100};
int target = 85;

[Link]("Sorted array: {10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100}");
[Link]("Target: " + target);

int result = fibonacciSearch(arr, target);

if (result != -1) {
[Link]("Element found at index: " + result);
} else {
[Link]("Element not found in the array.");
}
}
}

Program Output

Sorted array: {10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100}
Target: 85
 Element found at index: 8

Time & Space Complexity Analysis

Best Case O(1) Average Case O(log n)

Worst Case O(log n) Space Complexity O(1)

Why is it like this?

Fibonacci numbers grow at a rate close to the golden ratio (about 1.618) with each step, which is a similar growth rate to doubling. This means the
search range shrinks almost as fast as it does in Binary Search, so the number of steps needed is also proportional to log n, giving O(log n) overall.
Only a handful of Fibonacci-tracking variables are used, so space stays O(1).

Note: Comparable in complexity to Binary Search, but historically advantageous on hardware or storage media where addition and subtraction are cheaper
than division.

— End of Document —