Core · Module 9 · Lesson 4 of 4
Rotated and two-dimensional data
Binary search still works when sorted data has been rotated, because one half of any range is always sorted. Sorted grids can be searched as one long array, or with a staircase walk from a corner.
Pro — members onlyAbout 14 minutes
By the end you can
- Search a rotated sorted array in O(log n) by finding the sorted half at each step
- Find the rotation point, the minimum, with a single comparison per step
- Search sorted matrices with flat-index binary search or a staircase walk, and know which applies
Builds on Searching an answer space.
01 · A question first
A sorted array was rotated: [4, 5, 6, 7, 0, 1, 2]. It is no longer sorted, yet you can still find any value in O(log n) comparisons. What property survives the rotation?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- When the order is only partly there
- Rotated arrays
- Finding the rotation point
- Two-dimensional data
- The common thread
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
- Complexity Derivation, Edge Cases & Common Mistakes
03 · Practice
Practice · medium · LeetCodeSearch in rotated sorted arrayFind a target in a sorted array that has been rotated, in O(log n), by identifying the sorted half at each step.Practice · medium · LeetCodeFind minimum in rotated sorted arrayFind the smallest element of a rotated sorted array in O(log n) by comparing the middle with the right end.Practice · medium · LeetCodeSearch a 2D matrixSearch a matrix whose rows continue each other in sorted order, as one flat sorted array of m × n elements.Practice · medium · LeetCodeSearch a 2D matrix IISearch a matrix whose rows and columns are sorted independently, in O(m + n), with a staircase walk from the top-right corner.
Asked in interviews
Something wrong with this lesson? Report a problem