Binary Search in a Shifted Array | Skilled.dev
Interview Question

Shifted Search

Given a shifted array of sorted unique integers, write a function findTargetIndex that returns the index of a target value.

You are given an array of sorted integers that has been shifted by an unknown number of spots. For example:

  • Original array: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  • Shifted array: [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]

It is the same values in the same order but with the array rotated.

You can assume all the numbers in the array are unique.

If the number doesn't exist in the array, you should return -1.

const items = [3, 4, 5, 6, 7, 8, 0, 1, 2];
const target = 5;
findTargetIndex(items, target) // 2

Breakdown

Loading...

Table of Contents

Validate My Answer

  1. Ensure you have handled both cases where the target exists and doesn't exist in the input array.

  2. Since the array is mostly sorted, you can still use a modified version of binary search to get O(log n) time.

Loading...

Table of Contents

Test Results

Run your code and see results here...

const findTargetIndex = (items, target) => {
  // Your solution here
}
// Upgrade for full course access
// Upgrade for full course access

Shifted Search

Given a shifted array of sorted unique integers, write a function findTargetIndex that returns the index of a target value.

You are given an array of sorted integers that has been shifted by an unknown number of spots. For example:

  • Original array: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  • Shifted array: [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]

It is the same values in the same order but with the array rotated.

You can assume all the numbers in the array are unique.

If the number doesn't exist in the array, you should return -1.

const items = [3, 4, 5, 6, 7, 8, 0, 1, 2];
const target = 5;
findTargetIndex(items, target) // 2
const findTargetIndex = (items, target) => {
  // Your solution here
}
// Upgrade for full course access
// Upgrade for full course access