Searching and Sorting Master Guide

Most problems boil down to: find efficiently or order efficiently. This guide teaches how to recognize the correct searching or sorting approach, when to switch to specialized variants, and how to implement them with small Java templates.

---

How to Use This Guide

• Read the identification cues to map a problem to a search/sort family.
• Start with the Java template, then adapt boundary conditions or comparators.
• Practice 3 problems per topic; after each, write what went wrong and why.
• Prefer clarity over micro-optimizations.

---

Table of Contents

• Linear Search
• Binary Search (Index)
• Binary Search on Answer
• Ternary Search (Unimodal)
• Exponential Search
• Interpolation Search (Theory)
• Sorting Basics (Stability, In-place)
• Selection Sort
• Insertion Sort
• Bubble Sort (Educational)
• Merge Sort
• Quick Sort
• Heap Sort
• Counting Sort
• Radix Sort
• Bucket Sort
• Top-K with Heaps
• Custom Sorting with Comparators
• Frequency-based Sorting

---

Linear Search

Identify when:

• Small arrays or trivial scan needed.
• As a building block inside other algorithms.

Java template:

int indexOf(int[] a, int target){
  for (int i = 0; i < a.length; i++) if (a[i] == target) return i;
  return -1;
}

LeetCode set: Find the Town Judge 997 (scan degrees); First Bad Version 278 (baseline vs binary); Check if N and Its Double Exist 1346.

---

Binary Search (Index)

Identify when:

• Array is sorted, or you can sort without breaking constraints.
• Need index, lower bound, upper bound, or first/last occurrence.

Visual:

lo .... mid .... hi (predicate monotonic)

Java template (leftmost >= target):

int lowerBound(int[] a, int target){
  int lo = 0, hi = a.length - 1, ans = a.length;
  while (lo <= hi){
    int mid = lo + (hi - lo) / 2;
    if (a[mid] >= target){ ans = mid; hi = mid - 1; }
    else lo = mid + 1;
  }
  return ans;
}

Variants:

• First true / last false; first occurrence / last occurrence.
• Boundary on custom predicate; binary search on rotated arrays.

LeetCode set: Binary Search 704; Search Insert Position 35; Find First and Last Position 34; Search in Rotated Sorted Array 33; Find Minimum in Rotated Sorted Array 153.

---

Binary Search on Answer

Identify when:

• Answer lies in a numeric range and feasibility is monotonic.
• Typical in partitioning, capacity, or time minimization problems.

Java template:

long solve(){
  long lo = L, hi = R, ans = -1;
  while (lo <= hi){
    long mid = lo + (hi - lo) / 2;
    if (feasible(mid)){ ans = mid; hi = mid - 1; } // minimize
    else lo = mid + 1;
  }
  return ans;
}

LeetCode set: Koko Eating Bananas 875; Capacity To Ship Packages Within D Days 1011; Split Array Largest Sum 410; Min Speed On Time 1870.

---

Ternary Search (Unimodal)

Identify when:

• Function is unimodal (strictly increasing then decreasing or vice versa).
• Search for maximum/minimum of continuous or discrete function.

Java template (discrete):

int ternary(int lo, int hi){
  while (hi - lo > 2){
    int m1 = lo + (hi - lo) / 3;
    int m2 = hi - (hi - lo) / 3;
    if (f(m1) < f(m2)) lo = m1; else hi = m2;
  }
  int best = lo;
  for (int x = lo + 1; x <= hi; x++) if (f(x) > f(best)) best = x;
  return best;
}

Problems to explore: Maximum Value at a Given Index 1802 (can be solved via BS on answer; conceptually unimodal).

---

Exponential Search

Identify when:

• Unknown size stream or infinite array abstraction.
• Find bounds exponentially, then binary search.

Java template:

int expoSearch(int[] a, int x){
  if (a.length == 0) return -1;
  int bound = 1;
  while (bound < a.length && a[bound] < x) bound <<= 1;
  int lo = bound >> 1, hi = Math.min(bound, a.length - 1);
  // binary search in [lo, hi]
  while (lo <= hi){
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == x) return mid;
    if (a[mid] < x) lo = mid + 1; else hi = mid - 1;
  }
  return -1;
}

---

Interpolation Search (Theory)

Use rarely in interviews; assumes uniform distribution to guess position. Prefer binary search in practice.

---

Sorting Basics

Know these terms:

• Stable vs unstable; in-place vs extra memory.
• Comparison sort lower bound: O(n log n).
• Non-comparison sorts (counting, radix, bucket) rely on domain constraints.

Complexities (typical):

• Merge: O(n log n) time, O(n) space, stable.
• Quick: average O(n log n), worst O(n^2), in-place, unstable.
• Heap: O(n log n), in-place (array heap), unstable.

---

Selection Sort (Educational)

Java template:

for (int i = 0; i < n; i++){
  int min = i;
  for (int j = i + 1; j < n; j++) if (a[j] < a[min]) min = j;
  int t = a[i]; a[i] = a[min]; a[min] = t;
}

---

Insertion Sort

Identify when:

• Nearly sorted arrays; online insertion.

Java template:

for (int i = 1; i < n; i++){
  int key = a[i], j = i - 1;
  while (j >= 0 && a[j] > key){ a[j+1] = a[j]; j--; }
  a[j+1] = key;
}

LeetCode set: Insertion Sort List 147; Sort Colors 75 (3-way partition variant).

---

Bubble Sort (Educational)

Use only for teaching swaps and invariants.

---

Merge Sort

Identify when:

• Need stable sort; easy to adapt for counting inversions or merging k lists.

Java template:

void mergeSort(int[] a, int l, int r, int[] tmp){
  if (l >= r) return;
  int m = l + (r - l) / 2;
  mergeSort(a, l, m, tmp);
  mergeSort(a, m+1, r, tmp);
  int i=l, j=m+1, k=l;
  while (i<=m && j<=r){
    if (a[i] <= a[j]) tmp[k++] = a[i++]; else tmp[k++] = a[j++];
  }
  while (i<=m) tmp[k++] = a[i++];
  while (j<=r) tmp[k++] = a[j++];
  for (int t=l; t<=r; t++) a[t] = tmp[t];
}

LeetCode set: Merge Two Sorted Lists 21; Sort List 148; Count of Smaller Numbers After Self 315 (merge + counts).

---

Quick Sort

Identify when:

• In-place, average O(n log n), 3-way partition for many duplicates.

Java template (Lomuto):

int partition(int[] a, int l, int r){
  int pivot = a[r];
  int i = l;
  for (int j=l; j<r; j++){
    if (a[j] <= pivot){ int t=a[i]; a[i]=a[j]; a[j]=t; i++; }
  }
  int t=a[i]; a[i]=a[r]; a[r]=t;
  return i;
}
void quick(int[] a, int l, int r){
  if (l >= r) return;
  int p = partition(a, l, r);
  quick(a, l, p-1); quick(a, p+1, r);
}

Variant: Hoare partition; 3-way partition for duplicates.

LeetCode set: Kth Largest Element in an Array 215 (quickselect); Sort Colors 75 (Dutch flag); Largest Number 179 (custom comparator).

---

Heap Sort

Identify when:

• Need in-place O(n log n) without recursion limits.

Java template:

void heapSort(int[] a){
  int n=a.length;
  for(int i=n/2-1;i>=0;i--) siftDown(a,i,n);
  for(int end=n-1; end>0; end--){
    int t=a[0]; a[0]=a[end]; a[end]=t;
    siftDown(a,0,end);
  }
}
void siftDown(int[] a,int i,int n){
  while(true){
    int l=2*i+1, r=2*i+2, best=i;
    if(l<n && a[l]>a[best]) best=l;
    if(r<n && a[r]>a[best]) best=r;
    if(best==i) break;
    int t=a[i]; a[i]=a[best]; a[best]=t;
    i=best;
  }
}

---

Counting Sort

Identify when:

• Keys in small integer range [0..K].

Java template:

int[] countSort(int[] a, int K){
  int n=a.length; int[] cnt=new int[K+1];
  for(int x: a) cnt[x]++;
  for(int i=1;i<=K;i++) cnt[i]+=cnt[i-1];
  int[] out=new int[n];
  for(int i=n-1;i>=0;i--) out[--cnt[a[i]]] = a[i]; // stable
  return out;
}

LeetCode set: Sort Characters By Frequency 451 (freq then custom sort).

---

Radix Sort

Identify when:

• Integers with bounded digits (base 10 or base 2^k).

Java sketch (LSD, uses counting per digit):

void radixSort(int[] a){
  int max=0; for(int x: a) max=Math.max(max,x);
  for(int exp=1; max/exp>0; exp*=10) countByDigit(a,exp);
}

Problems: Maximum Gap 164 (radix or bucket); Sort Integers by The Number of 1 Bits 1356 (then comparator).

---

Bucket Sort

Identify when:

• Values roughly uniform over a range; near-linear expected time.

Example use: Maximum Gap 164 (bucket by range).

---

Top-K with Heaps

Identify when:

• Need k largest/smallest or stream processing.

Java template:

PriorityQueue<Integer> h = new PriorityQueue<>(); // min-heap
for(int x: a){
  h.offer(x);
  if(h.size()>k) h.poll();
}
// heap has k largest

LeetCode set: Top K Frequent Elements 347; Kth Largest Element 215; Find K Pairs With Smallest Sums 373.

---

Custom Sorting with Comparators

Identify when:

• Need domain-specific order.

Java template:

Arrays.sort(arr, (u,v) -> {
  // return negative if u before v, positive if after, 0 if equal
  return key(u) - key(v);
});

LeetCode set: Largest Number 179; Reorder Log Files 937; Sort the Jumbled Numbers 2191.

---

Frequency-based Sorting

Identify when:

• Sort by frequency, then by value or other tie-breakers.

Java template:

Map<Integer,Integer> f = new HashMap<>();
for(int x: a) f.put(x, f.getOrDefault(x,0)+1);
List<Integer> list = new ArrayList<>(f.keySet());
Collections.sort(list, (u,v) -> {
  int cu=f.get(u), cv=f.get(v);
  if (cu!=cv) return cv-cu; // desc by freq
  return u-v;
});

LeetCode set: Sort Characters By Frequency 451; Frequency Sort 1636; Relative Sort Array 1122.

---

Pitfalls and Checks

• Off-by-one in binary search (while condition, mid updates).
• Stability assumptions when merging or counting.
• Pivot choice in quick sort (3-way for duplicates).
• Overflow in mid = (lo+hi)/2 (use lo + (hi-lo)/2).
• Comparator must be anti-symmetric and transitive.

Practice Plan

• Day 1: Binary Search (index + on answer).
• Day 2: Merge Sort + Quick Sort.
• Day 3: Heaps (top-k, heap sort).
• Day 4: Counting/Radix/Bucket.
• Day 5: Custom sorting with comparators; frequency sort.
• Retrospective: write 5-line takeaways after each session.