Finding things and ordering things - these are the two most common operations in programming.
You've been searching since Module 1. The phone book problem? That was binary search. Checking if something exists in an array? That's linear search. Now you'll learn to implement both properly.
And sorting - why does it matter? Because sorted data makes many problems trivial. Finding a value in an unsorted array is O(n). In a sorted array, it's O(log n). Finding duplicates in an unsorted array might require a hash set; in a sorted array, they're right next to each other.
Many interview problems follow the pattern: "sort first, then solve." Learning when and how to sort is a superpower.
Linear search checks every element one by one until it finds the target. 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.
We first saw this in the Big O module with the phone book example. Now you'll implement it.
Key requirement: The array must be sorted. If you only need to search 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;
}| 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 problems |
When to use what:
Binary search is the most commonly tested in interviews, but knowing when linear search is actually the right choice 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) avg, O(n) worst | No |
| Heap Sort | O(n log n) | O(n log n) | O(1) | No |
Most languages have a built-in sort that's highly optimized. But understanding how these work is essential for interviews - and for knowing which one to reach for when a built-in won't do.
| Decision | Best Choice | Why |
|---|---|---|
| Small input (< 50 items) | Insertion Sort (or built-in) | Simple, fast on small data |
| General purpose, need speed | Quick Sort | In-place, fast average case |
| 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 | Preserves relative order of equal elements |
| Nearly sorted data | Insertion Sort | O(n) on nearly-sorted, minimal swaps |
| Don't care | Built-in sort | Optimized for general use |
Key trade-off: Quick sort is the interview favorite; learn it well. Merge sort is the "safe" choice with guaranteed performance. Heap sort wins on space.
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.
| Operation | Count |
|---|---|
| Passes | n-1 |
| Comparisons per pass | n-1, n-2, ..., 1 |
| Total comparisons | n(n-1)/2 ≈ O(n²) |
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: It sorts in-place, using O(log n) stack space on average (compared to Merge Sort's O(n) space). Worst case degrades to O(n) stack space.
Key risk: Worst-case O(n²) when pivot selection is poor - for example, always picking the last element on an already-sorted array. This is why good implementations use a random pivot or median-of-three.
Quick sort is the most commonly asked sorting implementation in interviews.
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.
Key advantage over Quick Sort: Guaranteed O(n log n) in all cases - no worst-case O(n²) trap.
Key disadvantage: Requires O(n) extra space for merging.
It's also stable - equal elements keep their original relative order. This matters when sorting by multiple criteria.
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)" Quick sort degrades to O(n²) on already sorted arrays if pivot selection is poor. Use random pivot selection or median-of-three.
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 average, O(n) worst). Don't claim "O(1) space" for merge sort.
A rotated sorted array is a sorted array that's been shifted. Example: [4, 5, 6, 7, 0, 1, 2].
This is a common interview challenge, not a core topic. Make sure you're comfortable with standard binary search before attempting this.
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];
}You now know how to search and sort efficiently. These skills will serve you well in every module that follows.
Next, we move from linear structures to hierarchical ones. Trees & Tries introduce the concept of parent-child relationships - data that branches instead of lining up in a row.
Trees are everywhere: file systems, HTML DOM, organizational charts, and decision processes. And binary search trees? They give you O(log n) search and insert - like binary search, but with fast insertions too.
Next up: Trees & Tries