Search Nearly Sorted Array - C++ Solution

1. Introduction

In this blog post, we will explore an interesting variant of the binary search algorithm - searching in a nearly sorted array. A nearly sorted array is one in which each element may be misplaced by up to one position from its correct sorted order. This requires a modification of the traditional binary search technique.

Problem

Given a nearly sorted array where each element might be misplaced by at most one position, the task is to efficiently search for a given target element and return its index.

2. Solution Steps

1. Implement a modified binary search.

2. Instead of just checking the middle element, also check the elements at mid-1 and mid+1 positions.

3. If the target is found at any of these positions, return the index.

4. Based on the comparison, decide whether to search in the left or the right half of the array.

5. Continue this process until the target is found or the search space is exhausted.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to search in a nearly sorted array
int searchNearlySorted(const vector<int>& nums, int target) {
    int low = 0, high = nums.size() - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        // Check for target at mid, mid-1, and mid+1 positions
        if (nums[mid] == target) {
            return mid;
        }
        if (mid > low && nums[mid - 1] == target) {
            return mid - 1;
        }
        if (mid < high && nums[mid + 1] == target) {
            return mid + 1;
        }

        // Move to the appropriate half of the array
        if (nums[mid] > target) {
            high = mid - 2;
        } else {
            low = mid + 2;
        }
    }

    return -1; // Target not found
}

int main() {
    vector<int> nums = {2, 1, 3, 5, 4, 7, 6, 8, 9};
    int target = 5;
    cout << "Index of target " << target << ": " << searchNearlySorted(nums, target) << endl;
    return 0;
}

Output:

Index of target 5: 3

Explanation:

The function searchNearlySorted uses a modified binary search to accommodate the nearly sorted nature of the array. It not only checks the middle element but also the adjacent elements to find the target. For the input array [2, 1, 3, 5, 4, 7, 6, 8, 9] with target 5, the target is found at index 3. This algorithm efficiently handles the slight disarray in the sorting, ensuring a fast search.