Searching in a Nearly Sorted Array

Problem Statement:

Given a sorted array where an element that should be present in i’th position, can be present in i-1’th position or i+1’th position. You are also given a key element. Check if the key element is present or not.

Example:

array = {1, 2, 3, 5, 4, 6, 7}; => Here element 4 is moved to next position and 5 is moved to previous position.
Key = 2
Output: Element found at index 1.

array = {2, 1, 3, 5, 4, 6, 8, 7}; => Here elements 2, 1 are moved, 5,4 are moved, 7, 8 are moved.
Key = 2
Output: Element found at index 0.

We can solve this by modified binary search.

Basically when we get the mid index, we check the key element with the element at mid index, mid+1 index, mid -1 index.

If we don’t find the key element, then we move to right part and left part appropriately.

While checking for mid-1 index, there are chances that we access negative index. So we have to check an additional condition, where “mid – 1 >= start”.

Similarly while checking mid+1 index, there are chances that we can access an index that is put of bound, so we have to do an additional check “mid + 1 <= end”

Solution in C++

#include <iostream>
using namespace std;

int search_element(int arr[], int length, int key)
{
    int start = 0;
    int end = length - 1;

    while (start <= end)
    {

        int mid = (start + end) / 2;

        //check if arr[mid] is equal to key
        if (arr[mid] == key)
            return mid;

        // return mid-1 if arr[mid - 1] is equal to key
        else if (mid - 1 >= start && arr[mid - 1] == key)
            return mid - 1;

        //  return mid+1 if arr[mid + 1] is equal to key
        else if (mid + 1 <= end && arr[mid + 1] == key)
            return mid + 1;

        // ignore the left half
        else if (key > arr[mid])
            start = mid + 2;

        // ignore the right half
        else
            end = mid - 2 ;
    }

    //key not found
    return -1;
}


int main(void) 
{ 
    int arr[] = {2, 1, 3, 5, 4, 6, 8, 7}; 
    int size = sizeof(arr) / sizeof(arr[0]); 
    int key = 2;

    int result = search_element(arr, size, key);

    cout<<" The key is found at index " <<result<<endl;

    return 0; 
} 

Output:

The key is found at index 0