Back to Subject

Unit 6: Searching techniques

CSE329 — Prelude To Competitive Coding 3 min read

Searching is the task of locating a target value, position, or property within a data collection. This unit builds from the two classical comparison searches through approximate and structural variants, then applies searching ideas to array, string, and optimization problems. Everything below rests on a few shared conventions.

  • Input assumptions: many searches require a sorted array; binary and jump search are invalid on unsorted data, so sorting cost (O(n log n)) is sometimes hidden in the setup.
  • Cost model: we count comparisons or array accesses; time complexity is stated in Big-O of the input size n.
  • Zero-based indexing: array a[0 .. n-1]; lo, hi denote inclusive bounds, mid = lo + (hi - lo) / 2 to avoid integer overflow.
  • Return convention: index of the found element, or -1 for "not present".

II. Comparison-based searches on sorted data

Halving and blocking strategies.

A. Iterative and recursive binary search

Binary search repeatedly halves a sorted range, discarding the half that cannot contain the target.

  • Iterative form: maintain a shrinking window and loop until it is empty.
    TEXT
      while lo <= hi:
      mid = lo + (hi - lo)/2
      if a[mid] == key: return mid
      if a[mid] < key:  lo = mid + 1
      else:             hi = mid - 1
  return -1
  • Recursive form: same logic, but the window is passed as arguments.
    TEXT
      bsearch(a, lo, hi, key):
      if lo > hi: return -1
      mid = lo + (hi - lo)/2
      if a[mid] == key: return mid
      if a[mid] < key:  return bsearch(a, mid+1, hi, key)
      else:             return bsearch(a, lo, mid-1, key)
  • Contrast the two:
    1. Iterative: O(1) auxiliary space; no call overhead.
    2. Recursive: O(log n) stack frames; cleaner but risks stack growth on huge ranges.
  • Complexity: each step discards half the range, so O(log₂ n) time; for n = 1,000,000 at most 20 comparisons.

B. Jump search

Jump search skips ahead in fixed blocks, then does a linear scan inside the block that must contain the key — a middle ground between linear and binary.

  • Block size: the optimal jump is √n, minimizing block-count plus in-block scan.
  • Procedure: jump step = √n while a[min(step,n)-1] < key; then linearly scan the previous block.
  • Complexity: O(√n), worse than binary but uses only forward stepping, useful when jumping back is cheap and binary's random jumps are not.
  • Example: n = 16, step = 4; searching for 55 in blocks […index 3], [index 7], … jumps to indices 3, 7, 11 before scanning within.

III. Structured search variants

Searching inside lists and rotated data.

A. Sublist search

Sublist search detects whether one linked list appears as a contiguous run inside another.

  • Purpose: pattern matching on lists where indexing is unavailable, so binary search cannot apply.
  • Method: for each node of the main list, walk both lists in lockstep; a full traversal of the sublist means a match.
  • Complexity: O(m × n) for lists of length m and n; naive but correct when random access is impossible.

B. Search an element in a sorted and rotated array

A sorted array rotated at an unknown pivot (e.g. [4,5,6,7,0,1,2]) can still be searched in logarithmic time because one half is always sorted.

  • Key insight: at any mid, either a[lo..mid] or a[mid..hi] is fully sorted.
  • Decision rule:
    TEXT
      if a[lo] <= a[mid]:               # left half sorted
      if a[lo] <= key < a[mid]: hi = mid-1
      else:                     lo = mid+1
  else:                             # right half sorted
      if a[mid] < key <= a[hi]: lo = mid+1
      else:                     hi = mid-1
  • Complexity: O(log n), single pass, no need to first find the pivot.

IV. Numeric and property searches

Deriving a value or an index from array structure.

A. Find the missing number

Given n-1 distinct numbers from 1 .. n, find the one absent value.

  • Sum method: expected total is n(n+1)/2; missing = expected − actual sum. O(n) time, O(1) space.
  • XOR method: XOR all indices 1..n with all array elements; pairs cancel, leaving the missing number. Avoids overflow that the sum method can hit.
  • Example: [1,2,4,5], n = 5: expected 15, actual 12, missing 3.

B. Find a pair with a given difference

Locate indices i, j with a[j] − a[i] = d.

  • Sort + two pointers: sort, then advance a slow/fast pointer; if difference too small advance fast, if too large advance slow.
    TEXT
      while i < n and j < n:
      if i != j and a[j]-a[i] == d: return (i,j)
      elif a[j]-a[i] < d: j++
      else: i++
  • Complexity: O(n log n) from the sort, then O(n) for the scan.
  • Hash alternative: store seen values, check for x + d or x − d in O(n) expected time.

C. Find a peak element

A peak is any element not smaller than its neighbours; edges compare against one side only.

  • Binary approach: move toward the larger neighbour, guaranteeing a peak lies that way.
    TEXT
      if a[mid] < a[mid+1]: lo = mid+1   # peak on the right
  else:                 hi = mid      # peak here or left
  • Complexity: O(log n); works even on unsorted arrays because it exploits local slope, not global order.
  • Example: [1,3,20,4,1,0] returns index 2 (value 20).

V. String searches

Locating substrings and ranking words.

A. Recursive function to perform substring search

Determine whether pattern p occurs in text t, expressed recursively rather than with loops.

  • Base cases: empty pattern matches at the current spot; exhausted text with pattern left means failure.
  • Step: compare a prefix; on mismatch, recurse on t advanced by one character.
    TEXT
      contains(t, p):
      if p == "": return true
      if t == "": return false
      if startsWith(t, p): return true
      return contains(t[1:], p)
  • Complexity: O(m × n) worst case for text length n, pattern length m.

B. Find the K most frequent words from a string

Rank the k words that appear most often, breaking ties alphabetically.

  • Count: tokenize on whitespace and tally in a hash map — O(n) over n words.
  • Select top k: push counts into a min-heap of size k, comparing by frequency then lexical order; heap keeps only the current best k.
  • Complexity: O(n log k); for small k far cheaper than fully sorting all distinct words.
  • Example: in "the day is sunny the the the sunny is is", k=2 → ["the"(4), "is"(3)].

VI. Range-sum searching problems

Searching for subarrays meeting a sum constraint.

A. Problems based on searching techniques

This class recasts a search as "find indices satisfying a numeric condition," using prefix sums, sliding windows, and binary search together.

  • Prefix sum: P[i] = a[0] + … + a[i-1], so any subarray sum = P[j] − P[i], converting subarray questions into pair questions on P.
  • Sliding window: valid only when all elements are non-negative, because then window sum is monotonic as bounds move.

B. Length of longest subarray having sum in given range l r

Find the maximum length of a contiguous block whose sum lies in [l, r].

  • Non-negative case: two windows — a right pointer for sum ≤ r, a left pointer maintaining sum ≥ l — track the widest gap.
  • General case: binary-search each prefix P[j] against sorted earlier prefixes to find an i with P[j] − P[i] ∈ [l, r].
  • Complexity: O(n) for the window variant, O(n log n) with binary search on prefixes.

C. Print all subarrays with sum in a given range

Enumerate every subarray whose sum falls within [l, r].

  • Count trick: count(sum ≤ r) − count(sum < l) gives the number of qualifying subarrays via merge-sort or BIT counting on prefix sums.
  • Enumeration: with non-negatives, slide a window; on each valid [left, right] emit all sub-windows still within range.
  • Complexity: O(n²) if every subarray is printed (output-bound), O(n log n) if only counted.

VII. Search applied to optimization

Binary search on the answer.

A. Minimum time required to produce m items

Given machines with per-item production rates, find the least time to make at least m items — solved by binary-searching the answer rather than the input.

  • Monotonicity: items producible in time T only grows with T, so a threshold time exists — the property binary search needs.
  • Feasibility check: at candidate time t, machine i (rate rᵢ) makes ⌊t / rᵢ⌋ items; sum across machines and test ≥ m.
    TEXT
      lo = 0, hi = min_rate * m
  while lo < hi:
      t = (lo + hi)/2
      if produced(t) >= m: hi = t
      else:                lo = t + 1
  return lo
  • Complexity: O(k log(minRate × m)) for k machines; the log factor is the binary search over the time axis.
  • Example: rates [1, 2], m = 5: at t = 6, machine 1 makes 6 and machine 2 makes 3 → 9 ≥ 5; the search narrows to the minimal such t = 4 (4 + 2 = 6 items).
Previous
Unit 5