Binary Search

2 problems using this pattern

About this pattern:

Divide and conquer on sorted data to achieve O(log n) search complexity.

Often used with: Two Pointers

Complexity Range

Time Complexity

O(log n) (2 problems)

Space Complexity

O(1) (2 problems)

Problems Using Binary Search

Binary Search

Search in sorted array of integers and return index if target is found.

Easy LeetCode
Time:
O(log n)?
Why O(log n)?
We halve the search space each iteration
Each comparison eliminates half of the remaining elements. We can eliminate at most log₂(n) halves.
Example: Array of 1000 elements needs max 10 comparisons (2¹⁰ = 1024)
Space:
O(1)?
Why O(1)?
Only using a few variables
We only store left, right, and mid pointers - constant space regardless of input size.
Example: Same memory usage for array of 10 or 10,000 elements
Example: nums = [-1,0,3,5,9,12], target = 9 → 4
Binary Search
View Solution →

Find First and Last Position

Find the starting and ending position of a given target value.

Medium LeetCode
Time: O(log n)
Space: O(1)
Example: nums = [5,7,7,8,8,10], target = 8 → [3,4]
Binary Search Two Pointers
View Solution →
← Back to All Patterns
View All Categories