Search in Rotated Sorted Array

Search in Rotated Sorted Array | AlgoChronicle

Step 1

Know these before you start

Tick what you already know

Concept video

Step 2

Try it on paper

5–10 minutes, no code yet

ProblemProblem statementThere is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly rotated at an unknown pivot index. Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.Read

Problem Description

There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly rotated at an unknown pivot index. Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Step 6

Get it accepted

All test cases pass

Step 7

Review it so it sticks

Re-solve from memory after

Solve it yourself before you look

Reading the solution first feels like progress, but it makes the next similar problem — and the interview version — much harder, because you skipped the part where you figure it out. Give it an honest 20–30 minutes. Stuck? Re-read the pattern, watch the concept video, or try the brute force first.

Hidden: approach · solution code · optimal solution

#searching#binary-search#arrays

Revising this one?

→Solve it from memory before peeking
→Say the pattern out loud, not just the code
→Explain it like you would to a friend
→Try it again in a different language