Sorting and Searching

binary search

Classic template:

1. l = 0, r = n-1

2. While l <= r:

   • mid = (l+r)//2

   • Compare target with nums[mid]

3. Move left/right accordingly

   O(log n)

Search in Rotated Sorted Array

Modified binary search:

1. One half is always sorted

2. Check if target lies in sorted half

3. Move to correct side

   Repeat until found

   O(log n)

Kth Smallest Element in a Sorted Matrix

Binary search on value range:

1. low = smallest, high = largest

2. Mid = candidate value

3. Count elements ≤ mid (row-wise)

4. If count < k → search right

5. Else search left

   O(n log range)

Search a 2D Matrix

Treat matrix as sorted array:

1. Index = mid // cols, mid % cols

2. Apply binary search

   Matrix is globally sorted

   O(log (m*n))

Kth Largest Element in an Array

Quickselect:

1. Choose pivot

2. Partition into > pivot and < pivot

3. Recurse on correct side

   Average O(n)

   (Heap alternative: size k min-heap → O(n log k))

Find Minimum in Rotated Sorted Array

Binary search:

1. Compare nums[mid] with nums[r]

2. If mid > r, min is right side

3. Else min is left (including mid)

   Stop when l == r

   O(log n)

Median of Two Sorted Arrays (H)

Binary search partition:

1. Partition both arrays so left halves = right halves

2. Ensure max(left) ≤ min(right)

3. Median from boundary elements

   Binary search on smaller array

   O(log(min(m,n)))

H-Index

Sort citations:

1. Sort descending

2. Find largest h such that citations[h] ≥ h+1

   Alternative:

• Sort ascending and check citations[i] ≥ n-i