Skip to main content

DSAPath16 mincore

bisect Patterns

bisect patterns use binary search helpers for sorted arrays, boundary counts, insertion points, and search-on-answer problems with monotone predicates.

DifficultyCore
TierTier 2
ModulePython Practice
LanguagesPython

Why This Matters

bisect turns boundary search into a standard operation. It is useful for sorted arrays, duplicate counts, insertion points, and problems where the answer is the smallest value satisfying a monotone predicate.

Core Idea

bisect_left finds the first valid insertion point. bisect_right finds the position after the last equal item.

MethodRole
bisect_left(a, x)first index where x could go
bisect_right(a, x)index after the rightmost x
insort(a, x)insert while keeping sorted order
custom searchbinary search over a monotone predicate

Non-Example or Failure Mode

bisect assumes sorted input. Also, insort performs O(log n) search but O(n) insertion because list elements must shift.

Runnable Drill

bisect boundaries and search-on-answer drill

Output will appear here.

Common Mistakes

MistakeCorrection
Calling bisect on unsorted data.Sort first or maintain sorted order.
Forgetting duplicate boundaries.Use bisect_left and bisect_right together.
Treating insort as O(log n).Search is O(log n), insertion shift is O(n).
Binary searching a non-monotone condition.State the monotone predicate before writing code.

Diagnostic Questions

Question typeQuestionAnswer signal
DefinitionWhat does bisect_left return?The first insertion point that keeps sorted order.
Example / non-exampleIs insort good for millions of middle insertions?Usually no; shifting dominates.
ComputationHow do you count duplicates of x?bisect_right(a, x) - bisect_left(a, x).
TransferWhat makes search-on-answer valid?A monotone predicate over candidate answers.

Exercises

Beginner:

  • Count how many times a value appears in a sorted list.
  • Insert values with insort and inspect the sorted result.
  • Find the first value greater than or equal to a target.

Intermediate:

  • Solve "minimum capacity to ship packages in D days."
  • Binary search the minimum feasible speed for a workload.

Challenge:

  • Prove your predicate is monotone before using search-on-answer.

References