Binary Search works on a sorted array by repeatedly dividing the search interval in half.

Algorithm (Iterative):

• Initialize low = 0 and high = n - 1.
• While low <= high:
  • Compute mid = low + (high - low) / 2 (avoids overflow).
  • If arr[mid] == key, return mid.
  • If arr[mid] < key, set low = mid + 1.
  • Else set high = mid - 1.
• Return -1 if not found.

Pseudocode:

int binarySearch(arr, n, key):
low = 0, high = n - 1
while low <= high:
mid = low + (high - low) / 2
if arr[mid] == key: return mid
elif arr[mid] < key: low = mid + 1
else: high = mid - 1
return -1

Time Complexity Derivation:

Each step halves the search space. If is the size, after steps the size is . Search ends when , giving .

• Time Complexity:
• Space Complexity: (iterative version uses constant space).

Comparison:

Recursive Implementation:

int binarySearch(arr, low, high, key):
if low > high: return -1
mid = low + (high - low) / 2
if arr[mid] == key: return mid
if arr[mid] < key:
return binarySearch(arr, mid + 1, high, key)
else:
return binarySearch(arr, low, mid - 1, key)

Space Complexity Discussion:

• The recursion depth equals the number of halvings, i.e., .
• Each recursive call consumes stack memory, so total auxiliary space is .
• The iterative version reuses the same variables, hence .

Both have the same time complexity of .

Jump Search is a searching algorithm for sorted arrays that checks fewer elements than linear search by jumping ahead in fixed steps.

Steps:

• Choose a block size (typically ).
• Jump forward in blocks of until arr[min(m, n)-1] >= key (found the block).
• Perform a linear search within the identified block.

Optimal Block Size Derivation:

Suppose block size is . In the worst case:

• Number of jumps = .
• Linear search inside block = comparisons.

Total comparisons: .

Differentiate and set to zero:

So the optimal block size is .

Time Complexity:

Note: Jump search lies between linear search and binary search in performance and requires the array to be sorted.

Sublist Search checks whether a given list (or linked list) is present as a contiguous sublist within another larger list.

Problem: Given two linked lists, determine if the first list appears as a continuous sequence in the second.

Algorithm:

• Let ptr1 point to the head of the sublist and ptr2 traverse the main list.
• For each starting position in the main list:
  • Reset ptr1 to the sublist head.
  • Compare elements one by one while they match.
  • If ptr1 reaches the end, the sublist is found.
  • Otherwise move to the next node in the main list and retry.
• Return true if found, else false.

Pseudocode:

bool sublistSearch(first, second):
if first == NULL: return true
if second == NULL: return false
ptr2 = second
while ptr2 != NULL:
ptr1 = first
p = ptr2
while ptr1 != NULL:
if p == NULL: return false
if ptr1.data != p.data: break
ptr1 = ptr1.next
p = p.next
if ptr1 == NULL: return true
ptr2 = ptr2.next
return false

Time Complexity: where and are the lengths of the two lists.

Space Complexity: .

Given an array of size with distinct numbers in range , we find the single missing number.

Method 1: Sum Formula

• Expected sum of to is .
• Compute actual array sum .
• Missing number .
• Time: , Space: .
• Caveat: Large may cause integer overflow.

Method 2: XOR Method

• XOR all numbers to into x1.
• XOR all array elements into x2.
• Missing number .
• Since , pairs cancel, leaving the missing value.
• Time: , Space: , no overflow risk.

Method 3: Sorting / Binary Search

• Sort the array, then binary-search for the first index where arr[i] != i+1.
• Time: , Space: .

Comparison:

The XOR method is generally preferred for its linear time and overflow safety.

A sorted and rotated array is a sorted array rotated at some unknown pivot, e.g., [4,5,6,7,0,1,2].

Key Idea: A modified binary search where at each step one half is always sorted.

Algorithm:

• Set low = 0, high = n - 1.
• While low <= high:
  • mid = low + (high - low)/2.
  • If arr[mid] == key, return mid.
  • If left half is sorted (arr[low] <= arr[mid]):
  • If arr[low] <= key < arr[mid], search left: high = mid - 1.
  • Else search right: low = mid + 1.
  • Else right half is sorted:
  • If arr[mid] < key <= arr[high], search right: low = mid + 1.
  • Else search left: high = mid - 1.
• Return -1 if not found.

Example: Search key = 0 in [4,5,6,7,0,1,2].

• low=0, high=6, mid=3 (arr[3]=7). Left half [4..7] sorted. 0 not in [4,7), go right: low=4.
• low=4, high=6, mid=5 (arr[5]=1). Left half [0..1] sorted. 0 in [0,1), go left: high=4.
• low=4, high=4, mid=4 (arr[4]=0). Found at index 4.

Time Complexity: .

Goal: Recursively determine if a pattern pat exists in a text txt.

Approach: Recursively compare pattern with the text starting at each index.

Pseudocode:

bool match(txt, pat):

Base case: empty pattern always matches

if pat.length == 0: return true
# Text exhausted but pattern remains
if txt.length == 0: return false
# Check prefix match, else shift text by one
if startsWith(txt, pat):
    return true
return match(txt.substring(1), pat)

bool startsWith(txt, pat):
if pat.length == 0: return true
if txt.length == 0: return false
if txt[0] != pat[0]: return false
return startsWith(txt.substring(1), pat.substring(1))

Working:

• startsWith recursively checks whether the pattern matches at the current position.
• If not, match recursively retries from the next index of the text.

Time Complexity: in the worst case, where = pattern length and = text length. This is the naive approach; advanced algorithms like KMP achieve .

Space Complexity: due to recursion stack.

Problem: Given a string, return the words with the highest frequency (ties broken alphabetically).

Approach:

1. Tokenize the string into words.
2. Count frequencies using a hash map (word -> count).
3. Use a min-heap of size ordered by (frequency, then reverse-lexicographic) to keep the top .
4. Extract results from the heap in the required order.

Data Structures Used:

• Hash Map (unordered_map) — for average frequency counting.
• Min-Heap / Priority Queue — to maintain the most frequent efficiently.

Pseudocode:

count = HashMap()
for word in words:
count[word] += 1
heap = MinHeap(size K, compare by freq then lexicographic)
for (word, freq) in count:
heap.push((freq, word))
if heap.size > K: heap.pop()
result = heap elements sorted descending by freq

Complexity Analysis:

• Counting: where is number of words.
• Heap operations: .
• Overall Time: .
• Space: for the map + for the heap.

Using sorting instead of a heap gives , so the heap is better when .

Problem: Given an array and a value , find a pair such that .

Approach 1: Brute Force

• Check all pairs with nested loops.
• Time: , Space: .

Approach 2: Sorting + Two Pointers

• Sort the array.
• Use two pointers i and j:
  • If arr[j] - arr[i] == d, pair found.
  • If arr[j] - arr[i] < d, increment j.
  • Else increment i.
• Time: (dominated by sorting), Space: .

Pseudocode (Sorting):

sort(arr)
i = 0, j = 1
while i < n and j < n:
if i != j and arr[j] - arr[i] == d: return true
elif arr[j] - arr[i] < d: j += 1
else: i += 1
return false

Approach 3: Hashing

• Insert all elements into a hash set.
• For each element x, check if x + d or x - d exists.
• Time: average, Space: .

Comparison:

Hashing is fastest; sorting is best when extra space is a constraint.

Definition: A peak element is an element that is greater than or equal to its neighbors. For arr[i], it is a peak if arr[i] >= arr[i-1] and arr[i] >= arr[i+1]. Boundary elements consider only their single neighbor.

Key Insight: There always exists a peak because moving towards a larger neighbor eventually reaches one.

Binary Search Approach:

• Set low = 0, high = n - 1.
• While low < high:
  • mid = low + (high - low)/2.
  • If arr[mid] < arr[mid + 1], a peak lies on the right: low = mid + 1.
  • Else a peak lies on the left half (including mid): high = mid.
• Return low (peak index).

Pseudocode:

int findPeak(arr, n):
low = 0, high = n - 1
while low < high:
mid = low + (high - low) / 2
if arr[mid] < arr[mid + 1]: low = mid + 1
else: high = mid
return low

Why it works: If the mid element is smaller than the next, an ascending slope guarantees a peak to the right. Otherwise a peak exists at or before mid.

Time Complexity: , Space: .

Problem: Given an array, find the length of the longest contiguous subarray whose sum lies within .

Approach using Prefix Sums:

• Compute prefix sum array where pre[i] = arr[0] + ... + arr[i-1].
• Sum of subarray (i, j) = pre[j+1] - pre[i].
• We want l <= pre[j+1] - pre[i] <= r.

For arrays with only positive numbers, a sliding window / two-pointer technique works efficiently:

• Maintain a window [start, end] and running sum.
• Expand end and shrink start to keep the sum within valid limits.
• Track the maximum valid window length.

Pseudocode (positive numbers, sliding window):

start = 0, sum = 0, maxLen = 0
for end in 0..n-1:
sum += arr[end]
while sum > r and start <= end:
sum -= arr[start]; start += 1
if l <= sum <= r:
maxLen = max(maxLen, end - start + 1)
return maxLen

Complexity:

• Sliding window (positive numbers): Time , Space .
• General arrays (with negatives): require prefix sums with an ordered structure (e.g., balanced BST / Fenwick tree) giving .

Note: The sliding window works because with positive numbers the prefix sum is monotonically increasing.

Problem: Print every contiguous subarray whose sum lies within .

Brute Force Approach:

• Fix a start index i.
• Extend the subarray by moving j from i to n-1, maintaining a running sum.
• Whenever l <= sum <= r, print the subarray arr[i..j].

Pseudocode:

for i in 0..n-1:
sum = 0
for j in i..n-1:
sum += arr[j]
if l <= sum <= r:
print arr[i..j]

Optimization (positive numbers):

Use the identity: count(sum <= r) - count(sum < l) with sliding windows. To find subarrays with sum at most x:

long atMost(x):
start = 0, sum = 0, count = 0
for end in 0..n-1:
sum += arr[end]
while sum > x: sum -= arr[start]; start += 1
count += (end - start + 1)
return count

Then number of valid subarrays = atMost(r) - atMost(l-1).

Complexity:

• Brute force (printing all): time — unavoidable if we must print each subarray, since there can be of them.
• Counting only (positive numbers): using sliding windows.

Problem: Given machines where machine takes time[i] units to produce one item, find the minimum total time to produce items (machines work in parallel).

Key Idea — Binary Search on Answer:

In time , machine can produce items. Total items produced in time is:

This function is monotonic in — more time never produces fewer items — so we can binary search on .

Algorithm:

• low = 1, high = min(time) * m (upper bound: fastest machine alone).
• While low < high:
  • mid = low + (high - low)/2.
  • If items(mid) >= m, this time is feasible: high = mid.
  • Else low = mid + 1.
• Return low.

Pseudocode:

long minTime(time[], m):
low = 1, high = min(time) * m
while low < high:
mid = low + (high - low)/2
total = sum(mid / time[i] for all i)
if total >= m: high = mid
else: low = mid + 1
return low

Complexity:

• Each feasibility check is .
• Binary search runs times.
• Total Time: .

This is a classic "binary search on the answer" pattern.

Comparison of Searching Techniques:

Detailed Notes:

• Linear Search: Checks each element sequentially. Works on unsorted data and linked lists. Simple but slow for large data.

• Binary Search: Repeatedly halves a sorted array. Fastest for large sorted arrays with random access.

• Jump Search: Jumps in blocks of , then linear scan within a block. Useful when jumping back is costly (e.g., certain storage systems), sitting between linear and binary in efficiency.

Use Cases:

• Use linear for small or unsorted data.
• Use binary for large sorted arrays.
• Use jump when binary search's back-and-forth is expensive but data is sorted.

Goal: Find the index of the minimum element (rotation pivot) in .

Idea: The minimum is the only element smaller than its previous element; equivalently, we search the unsorted half.

Algorithm:

low = 0, high = n - 1
while low < high:
mid = low + (high - low)/2
if arr[mid] > arr[high]: low = mid + 1 # min in right half
else: high = mid # min in left half (incl. mid)
return low # index of minimum

Trace for [7,8,9,1,2,3,4,5,6] (n = 9):

• low=0, high=8, mid=4 (arr[4]=2). arr[4]=2 <= arr[8]=6, so high=4.
• low=0, high=4, mid=2 (arr[2]=9). arr[2]=9 > arr[4]=2, so low=3.
• low=3, high=4, mid=3 (arr[3]=1). arr[3]=1 <= arr[4]=2, so high=3.
• Now low == high == 3. Loop ends.

Result: Minimum element is arr[3] = 1, at index 3. This confirms the array was rotated by 3 positions.

Time Complexity: .

Recurrence Setup:

In recursive binary search, each call:

• Does work (compute mid, one comparison).
• Recurses on one half of the array of size .

Thus the recurrence is:

with base case .

Solving via Master Theorem:

The general form is where:

• (one recursive call)
• (problem halved)

Compute the critical exponent: .

So , which matches . This is Case 2 of the Master Theorem where .

Result:

Alternative (Substitution): Expanding, .

Hence recursive binary search runs in time.

Problem: In a sorted array with duplicates, find the first and last index of a target key.

Idea: Modify binary search to keep searching even after finding a match, moving in a direction depending on whether we want the first or last occurrence.

First Occurrence:

int firstOccurrence(arr, key):
low = 0, high = n - 1, res = -1
while low <= high:
mid = low + (high - low)/2
if arr[mid] == key:
res = mid
high = mid - 1 # continue searching LEFT
elif arr[mid] < key: low = mid + 1
else: high = mid - 1
return res

Last Occurrence:

int lastOccurrence(arr, key):
low = 0, high = n - 1, res = -1
while low <= high:
mid = low + (high - low)/2
if arr[mid] == key:
res = mid
low = mid + 1 # continue searching RIGHT
elif arr[mid] < key: low = mid + 1
else: high = mid - 1
return res

Example: arr = [1,2,2,2,3,4], key = 2.

• First occurrence = index 1.
• Last occurrence = index 3.
• Count of occurrences = last - first + 1 = 3.

Time Complexity: for each search.

Setup: Machines take time = [1, 2, 3] units per item. In time , total items . We need this .

Bounds: low = 1, high = min(time) * m = 1 * 11 = 11.

Iterations:

1. low=1, high=11, mid=6: items . Feasible → high = 6.
2. low=1, high=6, mid=3: items $= 3 + 1 + 1 = 5 < 11. Not feasible → low = 4`.
3. low=4, high=6, mid=5: items $= 5 + 2 + 1 = 8 < 11. Not feasible → low = 6`.
4. low=6, high=6: loop ends.

Result: Minimum time required = 6 units.

Verification: At : machine1 makes 6, machine2 makes 3, machine3 makes 2, totaling items — exactly meeting the requirement. At only items are produced, which is insufficient.

Complexity: .

Binary Search on the Answer is a technique where, instead of searching over array indices, we binary search over the range of possible answers.

When is it Applicable?

The pattern applies when:

• The answer lies within a known numeric range [lo, hi].
• There exists a monotonic feasibility predicate check(x) — if x works then all values on one side also work.
• We can efficiently evaluate check(x) (usually in ).

Because of monotonicity, we can discard half the search space each step.

General Template:

lo, hi = minPossible, maxPossible
while lo < hi:
mid = lo + (hi - lo)/2
if check(mid): hi = mid # (for minimization)
else: lo = mid + 1
return lo

Example Problems:

1. Minimum time to produce items: Search over time ; check(T) = "can produce items in time ". Feasibility is monotonic in .

2. Allocate minimum pages / Ship packages within D days: Search over the maximum load/capacity; check(cap) = "can complete within the limit given capacity cap". Larger capacity is always feasible.

Complexity: , typically .

This pattern converts an optimization problem into a series of simpler decision problems.

Both techniques efficiently answer subarray sum queries, but they suit different scenarios.

Prefix Sum:

• Precompute pre[i] = arr[0] + ... + arr[i-1].
• Sum of subarray (i, j) in .
• Works with negative numbers.
• Often combined with a hash map to count subarrays with a target sum.
• Space: for the prefix array.

Sliding Window (Two Pointers):

• Maintains a running sum over a moving window [start, end].
• Expands/shrinks the window based on constraints.
• Requires monotonicity — typically works only with non-negative numbers, because shrinking the window must reliably decrease the sum.
• Space: .

Comparison Table:

When to Use:

• Use prefix sum (with hashing) when the array has negative values or you need to count subarrays with an exact sum.
• Use sliding window for arrays of positive numbers when finding the longest/shortest subarray satisfying a sum condition, since it is more space-efficient.