Search target in nearly sorted array

Problem

Given a nearly sorted array (where each element may be swapped with its adjacent elements), write an efficient algorithm to search for a target value. The element at index i can only be swapped with nums[i+1] or nums[i-1].

Examples

Example 1

Input: nums = [10, 3, 40, 20, 50, 80, 70], target = 40
Output: 2
Explanation: The target `40` is present at index `2` in the array.

Example 2

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

Solution

Method 1 – Binary Search for Nearly Sorted Array

Intuition

In a nearly sorted array, each element may be swapped with its adjacent elements. This means the target could be at index mid, mid-1, or mid+1 during binary search. By checking these three positions, we can efficiently locate the target even if it has been moved from its original sorted position.

Approach

1. Set start = 0, end = n - 1.
2. While start <= end:
   • Compute mid = (start + end) // 2.
   • If nums[mid] == target, return mid.
   • If mid > 0 and nums[mid-1] == target, return mid-1.
   • If mid < n-1 and nums[mid+1] == target, return mid+1.
   • If target < nums[mid], set end = mid - 2 (skip adjacent positions).
   • Else, set start = mid + 2.
3. If not found, return -1.

Code

C++

class Solution {
public:
    int searchNearlySorted(const std::vector<int>& nums, int target) {
        int n = nums.size();
        int start = 0, end = n - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (mid > 0 && nums[mid - 1] == target) {
                return mid - 1;
            }
            if (mid < n - 1 && nums[mid + 1] == target) {
                return mid + 1;
            }
            if (target < nums[mid]) {
                end = mid - 2;
            } else {
                start = mid + 2;
            }
        }
        return -1;
    }
};

Java

class Solution {
	public int searchNearlySorted(int[] nums, int target) {
		int n = nums.length, start = 0, end = n - 1;
		while (start <= end) {
			int mid = start + (end - start) / 2;
			if (nums[mid] == target) {
				return mid;
			}
			if (mid > 0 && nums[mid - 1] == target) {
				return mid - 1;
			}
			if (mid < n - 1 && nums[mid + 1] == target) {
				return mid + 1;
			}
			if (target < nums[mid]) {
				end = mid - 2;
			} else {
				start = mid + 2;
			}
		}
		return -1;
	}
}

Kotlin

class Solution {
	fun searchNearlySorted(nums: IntArray, target: Int): Int {
		val n = nums.size
		var start = 0
		var end = n - 1
		while (start <= end) {
			val mid = start + (end - start) / 2
			if (nums[mid] == target) {
				return mid
			}
			if (mid > 0 && nums[mid - 1] == target) {
				return mid - 1
			}
			if (mid < n - 1 && nums[mid + 1] == target) {
				return mid + 1
			}
			if (target < nums[mid]) {
				end = mid - 2
			} else {
				start = mid + 2
			}
		}
		return -1
	}
}

Python

class Solution:
	def search_nearly_sorted(self, nums: list[int], target: int) -> int:
		n = len(nums)
		start, end = 0, n - 1
		while start <= end:
			mid = start + (end - start) // 2
			if nums[mid] == target:
				return mid
			if mid > 0 and nums[mid - 1] == target:
				return mid - 1
			if mid < n - 1 and nums[mid + 1] == target:
				return mid + 1
			if target < nums[mid]:
				end = mid - 2
			else:
				start = mid + 2
		return -1

Rust

impl Solution {
	pub fn search_nearly_sorted(nums: &[i32], target: i32) -> i32 {
		let n = nums.len();
		let (mut start, mut end) = (0, n - 1);
		while start <= end {
			let mid = start + (end - start) / 2;
			if nums[mid] == target {
				return mid as i32;
			}
			if mid > 0 && nums[mid - 1] == target {
				return (mid - 1) as i32;
			}
			if mid < n - 1 && nums[mid + 1] == target {
				return (mid + 1) as i32;
			}
			if target < nums[mid] {
				if mid < 2 {
					break;
				}
				end = mid - 2;
			} else {
				start = mid + 2;
			}
		}
		-1
	}
}

TypeScript

class Solution {
	searchNearlySorted(nums: number[], target: number): number {
		const n = nums.length;
		let start = 0, end = n - 1;
		while (start <= end) {
			const mid = start + Math.floor((end - start) / 2);
			if (nums[mid] === target) {
				return mid;
			}
			if (mid > 0 && nums[mid - 1] === target) {
				return mid - 1;
			}
			if (mid < n - 1 && nums[mid + 1] === target) {
				return mid + 1;
			}
			if (target < nums[mid]) {
				end = mid - 2;
			} else {
				start = mid + 2;
			}
		}
		return -1;
	}
}

Complexity

• ⏰ Time complexity: O(log n) — Each step discards at least half the remaining elements, with a small constant overhead for checking adjacent positions.
• 🧺 Space complexity: O(1) — Only uses a constant amount of extra space.