Search in a Nearly Sorted Array

Medium

Problem Statement

Given an array where each element is at most `k` positions away from its sorted position (often k=1), find the index of a given target element. If the element is not present, return -1.

Examples

1Example 1

Input:

{
  "nums": [
    10,
    3,
    40,
    20,
    50,
    80,
    70
  ],
  "target": 40
}

Output:

2

2Example 2

Input:

{
  "nums": [
    10,
    3,
    40,
    20,
    50,
    80,
    70
  ],
  "target": 90
}

Output:

-1

3Example 3

Input:

{
  "nums": [
    5,
    10,
    30,
    20,
    40
  ],
  "target": 20
}

Output:

3