InternDoor

Find it in a turned list

Mediumbinary search · arrays

Reported in interviews at (where)

A list of different whole numbers was sorted in increasing order, then turned: some number of values were taken off the front and put back at the end, in order. That list is nums. For example [2, 5, 9, 12, 15, 18] could become [15, 18, 2, 5, 9, 12].

Return the position of target in nums, or -1 if it is not there. Aim for O(log n) time.

Example 1
Input
nums = [15,18,2,5,9,12]
target = 5
Output
3

5 sits at position 3.

Example 2
Input
nums = [15,18,2,5,9,12]
target = 7
Output
-1

7 is not in the list.

Example 3
Input
nums = [4]
target = 4
Output
0

A list of one.

Limits

  • 1 <= nums.length <= 100000
  • -10^9 <= nums[i], target <= 10^9
  • All values in nums are different.

Hints

Hint 1

Split the list in the middle: at least one half is in plain sorted order.

Hint 2

Check whether the target falls inside the sorted half; if not, look in the other one.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.