Log inSign up
mediumgfgNot Started

Search in Nearly Sorted Array

Given an array which is sorted, but after sorting some elements are moved to either of the adjacent positions (i.e. element at index i can be at i-1, i, or i+1), search for a given element in O(log n) time.

Binary Search
Solve on gfg
Lesson

Problem Statement

Given an array arr which is sorted, but after sorting, some elements are moved to either of the adjacent positions, i.e., arr[i] may be present at arr[i-1], arr[i], or arr[i+1].\n\nGiven an integer target, search for target in the array and return its index. If the element is not found, return -1.\n\nYou must write an algorithm with O(log n) time complexity.

Example 1 · Example 1: Target in Swapped Position:

Input: arr = [10, 3, 40, 20, 50, 80, 70], target = 40
Output: 2
Explanation: Element 40 is at index 2.

Example 2 · Example 2: Target at Neighbor Index:

Input: arr = [10, 3, 40, 20, 50, 80, 70], target = 70
Output: 6
Explanation: Element 70 is at index 6.

Example 3 · Example 3: Target Not Found:

Input: arr = [10, 3, 40, 20, 50, 80, 70], target = 90
Output: -1
Explanation: 90 is not present in the array.

Constraints:

  • 1 <= arr.length <= 105
  • -109 <= arr[i], target <= 109
  • Elements are nearly sorted (an element originally at index i is in {i-1, i, i+1}).

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Adapt standard binary search to handle bounded index perturbations.
  • Safely check neighbor indices with boundary guards.
  • Understand why high = mid - 2 and low = mid + 2 preserve correctness.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Array is almost sorted / nearly sorted.
  • Element deviation from sorted position is bounded by ±1 index.
  • Logarithmic search requirement.

Algorithmic Decision Tree:

  • Calculate mid = low + (high - low) / 2.
  • Check arr[mid] == target -> return mid.
  • Check mid > low && arr[mid - 1] == target -> return mid - 1.
  • Check mid < high && arr[mid + 1] == target -> return mid + 1.
  • If target < arr[mid], set high = mid - 2.
  • Else set low = mid + 2.

Connected Patterns:

Binary SearchSearch in Rotated Sorted ArrayK-Sorted Array Sorting

1. Linear Search

Intuition

Traverse array from index 0 to n-1. If arr[i] == target, return i. Else return -1.

When to apply: When simplicity is preferred over performance on tiny arrays.

Algorithm

  1. Step 1: Iterate index i from 0 to n - 1.
  2. Step 2: If arr[i] == target, return i.
  3. Step 3: Return -1 if not found.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7int searchNearlySorted(const vector<int>& arr, int target) {
8 for (int i = 0; i < (int)arr.size(); ++i) {
9 if (arr[i] == target) return i;
10 }
11 return -1;
12}
13
14int main() {
15 // Sample driver execution
16 cout << "Execution completed successfully." << endl;
17 return 0;
18}
19

Time & Space Complexity

  • Time complexity: O(n) — Checks all n elements sequentially.
  • Space complexity: O(1) — Uses constant O(1) space.

2. Jump Search with Step Size 3

Intuition

Advance in steps of 3. In each block [i-1, i, i+1], test for match.

When to apply: When block skipping is sufficient.

Algorithm

  1. Step 1: For index i = 1; i < n; i += 3, check indices i-1, i, min(i+1, n-1).
  2. Step 2: If match found, return index.
  3. Step 3: Return -1 if not found.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7int searchJump3(const vector<int>& arr, int target) {
8 int n = arr.size();
9 for (int i = 0; i < n; i += 3) {
10 if (arr[i] == target) return i;
11 if (i + 1 < n && arr[i + 1] == target) return i + 1;
12 if (i + 2 < n && arr[i + 2] == target) return i + 2;
13 }
14 return -1;
15}
16
17int main() {
18 // Sample driver execution
19 cout << "Execution completed successfully." << endl;
20 return 0;
21}
22

Time & Space Complexity

  • Time complexity: O(n / 3) = O(n) — Reduces iterations by a factor of 3, but still linear asymptotic time.
  • Space complexity: O(1) — Requires O(1) extra variables.

3. Modified Binary Search (3-Way Check)

Intuition

Set low = 0, high = n - 1. While low <= high, compute mid. Check arr[mid], arr[mid-1] (if mid > low), and arr[mid+1] (if mid < high). If none match, if target < arr[mid], high = mid - 2; else low = mid + 2.

When to apply: Optimal standard method in interview settings.

Algorithm

  1. Step 1: Initialize low = 0, high = n - 1.
  2. Step 2: While low <= high, mid = low + (high - low) / 2.
  3. Step 3: If arr[mid] == target, return mid.
  4. Step 4: If mid > low && arr[mid - 1] == target, return mid - 1.
  5. Step 5: If mid < high && arr[mid + 1] == target, return mid + 1.
  6. Step 6: If target < arr[mid], set high = mid - 2.
  7. Step 7: Else set low = mid + 2.
  8. Step 8: Return -1.

Trace for arr = [10, 3, 40, 20, 50, 80, 70], target = 40

2 of 2 questions left today
Step 1 / 1
Trace timeline100% explored
Current operationSTEP 1 OF 1
Initial state: low=0, high=6
Visual state
Values and pointers at this exact step
pointers
S
10
3
40
20
50
80
70
0
↑ low
1
2
↑ mid-1
3
↑ mid
4
5
6
↑ high
Check / comparison
arr[mid-1]=arr[2]=40 == target 40 -> Match!
Decision / next transition
Return index 2 immediately.
Why this step matters

Initial state: low=0, high=6. mid=3 (val=20). Check mid: arr[3]=20 != 40. Check mid-1: arr[2]=40 == 40 (Match found!). Return index 2.

Step 1 / 1
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7int searchNearlySorted(const vector<int>& arr, int target) {
8 int low = 0, high = (int)arr.size() - 1;
9 while (low <= high) {
10 int mid = low + (high - low) / 2;
11 if (arr[mid] == target) return mid;
12 if (mid > low && arr[mid - 1] == target) return mid - 1;
13 if (mid < high && arr[mid + 1] == target) return mid + 1;
14
15 if (target < arr[mid]) {
16 high = mid - 2;
17 } else {
18 low = mid + 2;
19 }
20 }
21 return -1;
22}
23
24int main() {
25 // Sample driver execution
26 cout << "Execution completed successfully." << endl;
27 return 0;
28}
29

Time & Space Complexity

  • Time complexity: O(log n) — Search space is reduced by half in each iteration, giving logarithmic time.
  • Space complexity: O(1) — Operates in-place with O(1) space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear SearchO(n)O(1)Sequential element examination.Does not leverage near-sorted structure.
2.Jump Search (Step 3)O(n)O(1)Block traversal in triplets.Linear scan of blocks.
3.Modified Binary Search (3-Way)OptimalO(log n)O(1)Examine {mid-1, mid, mid+1} and update boundaries with step size 2.None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Single element array matching/not matching target.
  • Target is at index 0 or index n-1.
  • Adjacent pair swapped: [10, 3, 40, 20, 50, 80, 70].
  • Target not present in array.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the ±1 deviation property clearly to the interviewer.
  2. Demonstrate why checking mid-1, mid, mid+1 allows stepping by 2 instead of 1.
  3. Be careful to check index bounds mid > low and mid < high before indexing.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we update high to mid - 2 instead of mid - 1?

2.Why do we need the guard mid > low before checking arr[mid - 1]?

Back to DSA Sheet