Linear search checks every element one by one until the target is found. It's the simplest search - no preprocessing needed, works on any data.
| Linear Search | |
|---|---|
| Time | O(n) |
| Space | O(1) |
| Requires sorted? | No |
When to use:
Despite being "slow" on paper, linear search is often the right choice for small inputs.
// Linear search - O(n)
int LinearSearch(int[] arr, int target) {
for (int i = 0; i < arr.Length; i++)
if (arr[i] == target) return i;
return -1;
}
// Find all occurrences
List<int> FindAll(int[] arr, int target) {
var result = new List<int>();
for (int i = 0; i < arr.Length; i++)
if (arr[i] == target) result.Add(i);
return result;
}Binary search finds an element in a sorted array by repeatedly dividing the search range in half. Each step eliminates half the remaining elements.
Key requirement: The array must be sorted. If you need to search only once, sorting just to use binary search may not be worth it - linear search might be faster.
Binary search variants:
// Standard binary search - O(log n)
int BinarySearch(int[] arr, int target) {
int left = 0, right = arr.Length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
// Lower bound - first index where arr[i] >= target
int LowerBound(int[] arr, int target) {
int left = 0, right = arr.Length;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target) left = mid + 1;
else right = mid;
}
return left;
}
// Upper bound - first index where arr[i] > target
int UpperBound(int[] arr, int target) {
int left = 0, right = arr.Length;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] <= target) left = mid + 1;
else right = mid;
}
return left;
}A rotated sorted array is a sorted array that has been shifted. Example: [4, 5, 6, 7, 0, 1, 2].
Key insight: One half of the array is always normally sorted. Determine which half, then search accordingly.
int SearchRotated(int[] arr, int target) {
int left = 0, right = arr.Length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
// Left half is sorted
if (arr[left] <= arr[mid]) {
if (target >= arr[left] && target < arr[mid])
right = mid - 1;
else
left = mid + 1;
}
// Right half is sorted
else {
if (target > arr[mid] && target <= arr[right])
left = mid + 1;
else
right = mid - 1;
}
}
return -1;
}
// Find minimum in rotated array
int FindMin(int[] arr) {
int left = 0, right = arr.Length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] > arr[right])
left = mid + 1; // min is in right half
else
right = mid; // min is in left half (including mid)
}
return arr[left];
}| Algorithm | Time | Space | Sorted? | Best For |
|---|---|---|---|---|
| Linear Search | O(n) | O(1) | No | Small/unsorted |
| Binary Search | O(log n) | O(1) | Yes | Large sorted |
| BS on Answer | O(log range) | O(1) | Predicate | Optimization |
| DFS/BFS | O(V + E) | O(V) | No | Graph/tree |
When to use what:
Binary search is the most commonly tested in interviews, but knowing when linear search is actually the right choice (small n, unsorted data) is just as important.
| Algorithm | Average Time | Worst Time | Space | Stable |
|---|---|---|---|---|
| Bubble Sort | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(1) | No |
| Insertion Sort | O(n²) | O(n²) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n²) | O(log n) | No |
| Heap Sort | O(n log n) | O(n log n) | O(1) | No |
Most languages have a built-in sort that uses introsort (quick sort + heap sort fallback) for primitive types and a stable sort for reference types. The sections below cover the key algorithms you need to know for interviews.
Not all sorting algorithms are equal. The right choice depends on data size, structure, and requirements.
| Decision | Best Choice | Why |
|---|---|---|
| Small input (< 50 items) | Insertion Sort (or built-in) | Simple, fast on small data, stable |
| General purpose, need speed | Quick Sort | In-place, fast average case, built-in default |
| Need guaranteed O(n log n) | Merge Sort or Heap Sort | No O(n²) worst case |
| Limited memory (O(1) space) | Heap Sort | O(n log n) time, O(1) space |
| Need stable sort | Merge Sort (or Insertion) | Preserves relative order of equal elements |
| Nearly sorted data | Insertion Sort or Bubble Sort | O(n) on nearly-sorted, minimal swaps |
| Mostly sorted, online (streaming) | Insertion Sort | Efficiently adds one element at a time |
| Don't care, just want it sorted | Built-in sort (introsort) | Combines quick + heap + insertion, optimized |
Key trade-off: Quick sort is the interview favorite; learn it well. Merge sort is the "safe" choice. Heap sort wins on space. Insertion sort wins on tiny/nearly-sorted data.
Interview tip: Always ask about constraints before choosing. "Is the data nearly sorted? Do we need stability? What's the input size?"
Bubble sort repeatedly steps through the array, swapping adjacent elements if they're in the wrong order. Larger elements "bubble up" to their correct position with each pass.
Why learn it: It's the simplest sort to understand and teaches the concept of swapping. Why NOT to use it: O(n²) makes it impractical for real data. You'll rarely be asked to implement it, but it tests whether you understand basic sorting mechanics.
| Operation | Count |
|---|---|
| Passes | n-1 |
| Comparisons per pass | n-1, n-2, ..., 1 |
| Total comparisons | n(n-1)/2 ≈ O(n²) |
Use the interactive demo below to watch each pass bubble the largest unsorted element to its correct position.
Given an unsorted array, arrange the numbers in ascending order by repeatedly swapping adjacent elements that are out of order.
void BubbleSort(int[] arr) {
int n = arr.Length;
for (int i = 0; i < n - 1; i++) {
bool swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
(arr[j], arr[j + 1]) = (arr[j + 1], arr[j]);
swapped = true;
}
}
if (!swapped) break; // optimization: already sorted
}
}Quick sort picks a pivot, partitions the array so all elements ≤ pivot come before it, then recursively sorts each side.
Key advantage over merge sort: in-place sorting (O(log n) stack space vs O(n) space). Trade-off: worst-case O(n²) when pivot selection is poor (e.g., already sorted array with pivot at end).
Quick sort is the most commonly asked sorting implementation in interviews.
Use the interactive demo below to watch the pivot selection, partitioning, and recursive sorting.
Given an unsorted array, arrange the numbers in ascending order by selecting a pivot, partitioning around it, and recursing on both sides.
void QuickSort(int[] arr, int left, int right) {
if (left >= right) return;
int pivot = Partition(arr, left, right);
QuickSort(arr, left, pivot - 1);
QuickSort(arr, pivot + 1, right);
}
int Partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
i++;
(arr[i], arr[j]) = (arr[j], arr[i]);
}
}
(arr[i + 1], arr[right]) = (arr[right], arr[i + 1]);
return i + 1;
}Merge sort is a divide and conquer algorithm that splits the array in half, recursively sorts each half, then merges the sorted halves. It's stable and guarantees O(n log n) in all cases.
Key advantage over quick sort: predictable O(n log n) worst-case performance. Trade-off: requires O(n) extra space.
Use the interactive demo below to watch the recursive splitting and merging in action.
Given an unsorted array, arrange the numbers in ascending order by repeatedly splitting in half, sorting each half, then merging the sorted halves.
// Merge sort - O(n log n) time, O(n) space
int[] MergeSort(int[] arr) {
if (arr.Length <= 1) return arr;
int mid = arr.Length / 2;
var left = MergeSort(arr[..mid]);
var right = MergeSort(arr[mid..]);
return Merge(left, right);
}
int[] Merge(int[] left, int[] right) {
var result = new int[left.Length + right.Length];
int i = 0, j = 0, k = 0;
while (i < left.Length && j < right.Length)
result[k++] = left[i] <= right[j] ? left[i++] : right[j++];
while (i < left.Length) result[k++] = left[i++];
while (j < right.Length) result[k++] = right[j++];
return result;
}Binary search off-by-one: left < right vs left <= right
Use left <= right when searching for an exact value (standard binary search). Use left < right when narrowing to a single position (lower bound, rotated array min). Getting this wrong causes infinite loops or missed elements.
Forgetting to sort before binary search Binary search requires a sorted array. Searching an unsorted array with binary search gives random results.
Sorting without a custom comparator for non-default ordering
In JavaScript, .sort() defaults to lexicographic sort: [1, 2, 10].sort() = [1, 10, 2]. Always pass a comparator: .sort((a, b) => a - b).
Confusing stable vs unstable sort A stable sort preserves the relative order of equal elements. Merge sort is stable; quick sort is not. This matters when sorting by multiple criteria (e.g., sort by date, then by priority).
"Quicksort is always O(n log n)" Quicksort degrades to O(n²) on already sorted arrays if pivot selection is poor. Use random pivot selection or median-of-three to avoid this.
In-place vs non-in-place confusion Merge sort creates new arrays (O(n) space). Quick sort sorts in-place (O(log n) stack space). Don't claim "O(1) space" for merge sort.