Search in an almost sorted array

October 18, 2024

Search in an almost sorted array

In Search in an almost sorted array problem, we have to find the index of an element in the array. The problem can be solved optimally using the binary search technique. The problem is asked in many interviews. In this article, we will provide a C++ solution with an explanation.

Search in an almost sorted array Problem Description

Search in an almost sorted array Problem Description

Given an array of n integers and a integer x. Find the index of x in the array such that the array is almost sorted. By almost sorted we mean that the array elements will be present at most at adjacent positions (if not placed correctly) from their correct position in sorted order.

Example –

1 3 2 – is an almost sorted array. 2 & 3 have been swapped.

2 1 3 5 4 – is an almost sorted array. 1 & 2 is swapped and 4 & 5 are swapped.

Example –

3 2 4 1 is a wave

But 1 2 3 is not a wave.

Input:

  • First line contains two integers n & x – the size of the array & element to search.
  • Next Line contains n integers the elements of the array.

Output:

  • Index of the element x in the array or -1 if not found.

Search in an almost sorted array Problem Solution

Naive Approach –

The simple or naive approach is to use linear search. Traverse the array in a single loop and return the index of element if found or return -1 if not found.

Time Complexity – O(n), as we are using a single loop to traverse the array.

Space Complexity – O(1)

Code

Run 
#include <bits/stdc++.h>
using namespace std;
int find(int arr[], int n, int x)
{
    for (int i = 0; i < n; i++)
        if (arr[i] == x)
            return i;

    // If not found
    return -1;
}
int main()
{
    int n = 6;
    int arr[n] = {50, 30, 300, 200, 400, 560, 700};
    //sorted array -> 30 50 200 300 400 560 700
    int x = 300;
    cout << find(arr, n, x) << endl;
    return 0;
}

Output

2

Optimized Approach –

We know the best approach to search the element when it is sorted is Binary Search. Here, the array is not completely sorted but almost sorted. So we have to modify our binary search for this problem.

So while checking the middle element of our range we will also check it’s adjacent positions. If the element is found at any of these indexes we will simply return the index.

If the arr[mid] < x => we will search in range (mid+2,end) as we have already checked mid+1.

Similarly if arr[mid] > x => we will search in range (start,mid-2).

Time Complexity – O(n)

Space Complexity – O(1)

Code

Run 
#include <bits/stdc++.h>
using namespace std;
int find(int arr[], int n, int x)
{
    int st = 0, ed = n - 1;
    while (st <= ed)
    {
        int mid = (st + ed) / 2;
        if (arr[mid] == x)
            return mid;
        if (mid > 0 && arr[mid - 1] == x)
            return mid - 1;
        if (mid < n - 1 && arr[mid + 1] == x)
            return mid + 1;

        if (arr[mid] > x)
        {
            ed = mid - 2;
        }
        else
        {
            st = mid + 2;
        }
    }
    // Not Found
    return -1;
}
int main()
{
    int n = 6;
    int arr[n] = {50, 30, 300, 200, 400, 560, 700};
    //sorted array -> 30 50 200 300 400 560 700
    int x = 300;
    cout << find(arr, n, x) << endl;
    return 0;
}

Output

2

2 comments on “Search in an almost sorted array”


  • Avothu Sharath

    I couldn’t understand these problem because at the last three elements of an array were not swapped there is no action on that three elements what can do if user can take their own inputs please explain how can we solved the problem based on the user input