Search in an almost sorted array | GeeksforGeeks

Given an array 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] or arr[i-1]. Write an efficient function to search an element in this array. Basically the element arr[i] can only be swapped with either arr[i+1] or arr[i-1].

The idea is to compare the key with middle 3 elements, if present then return the index. If not present, then compare the key with middle element to decide whether to go in left half or right half. Comparing with middle element is enough as all the elements after mid+2 must be greater than element mid and all elements before mid-2 must be smaller than mid element.

int binarySearch(int arr[], int l, int r, int x)

{

   if (r >= l)

   {

        int mid = l + (r - l)/2;

        // If the element is present at one of the middle 3 positions

        if (arr[mid] == x)  return mid;

        if (mid > l && arr[mid-1] == x) return (mid - 1);

        if (mid < r && arr[mid+1] == x) return (mid + 1);

        // If element is smaller than mid, then it can only be present

        // in left subarray

        if (arr[mid] > x) return binarySearch(arr, l, mid-2, x);

        // Else the element can only be present in right subarray

        return binarySearch(arr, mid+2, r, x);

   }

   // We reach here when element is not present in array

   return -1;

}

Read full article from Search in an almost sorted array | GeeksforGeeks