Buscar en una array casi ordenada

Dada una array que está ordenada, pero después de ordenar algunos elementos se mueven a cualquiera de las posiciones adyacentes, es decir, arr[i] puede estar presente en arr[i+1] o arr[i-1]. Escriba una función eficiente para buscar un elemento en esta array. Básicamente, el elemento arr[i] solo se puede intercambiar con arr[i+1] o arr[i-1].
Por ejemplo, considere la array {2, 3, 10, 4, 40}, 4 se mueve a la siguiente posición y 10 se mueve a la posición anterior.
Ejemplo : 
 

Input: arr[] =  {10, 3, 40, 20, 50, 80, 70}, key = 40
Output: 2 
Output is index of 40 in given array

Input: arr[] =  {10, 3, 40, 20, 50, 80, 70}, key = 90
Output: -1
-1 is returned to indicate element is not present

Una solución simple es buscar linealmente la clave dada en una array dada. La complejidad temporal de esta solución es O(n). Podemos modificar la búsqueda binaria para hacerlo en tiempo O(Logn). 
La idea es comparar la clave con los 3 elementos del medio, si está presente, devolver el índice. Si no está presente, compare la clave con el elemento central para decidir si debe ir en la mitad izquierda o en la mitad derecha. Comparar con el elemento medio es suficiente ya que todos los elementos después de mid+2 deben ser mayores que el elemento mid y todos los elementos antes de mid-2 deben ser más pequeños que el elemento mid.
A continuación se muestra la implementación de este enfoque.
 

// C++ program to find an element
// in an almost sorted array
#include <stdio.h>
 
// A recursive binary search based function.
// It returns index of x in given array
// arr[l..r] is present, otherwise -1
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;
}
 
// Driver Code
int main(void)
{
int arr[] = {3, 2, 10, 4, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 4;
int result = binarySearch(arr, 0, n - 1, x);
(result == -1) ? printf("Element is not present in array")
               : printf("Element is present at index %d",
                         result);
return 0;
}

// Java program to find an element
// in an almost sorted array
class GFG
{
    // A recursive binary search based function.
    // It returns index of x in given array
    // arr[l..r] is present, otherwise -1
    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;
    }
 
    // Driver code
    public static void main(String args[])
    {
        GFG ob = new GFG();
        int arr[] = {3, 2, 10, 4, 40};
        int n = arr.length;
        int x = 4;
        int result = ob.binarySearch(arr, 0, n - 1, x);
        if(result == -1)
            System.out.println("Element is not present in array");
        else
            System.out.println("Element is present at index " +
                                result);
    }
}
 
// This code is contributed by Rajat Mishra

# Python 3 program to find an element
# in an almost sorted array
 
# A recursive binary search based function.
# It returns index of x in given array arr[l..r]
# is present, otherwise -1
def binarySearch(arr, l, r, x):
 
    if (r >= l):
         
        mid = int(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 and arr[mid - 1] == x):
            return (mid - 1)
        if (mid < r and 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
 
# Driver Code
arr = [3, 2, 10, 4, 40]
n = len(arr)
x = 4
result = binarySearch(arr, 0, n - 1, x)
if (result == -1):
    print("Element is not present in array")
else:
    print("Element is present at index", result)
 
# This code is contributed by Smitha Dinesh Semwal.

// C# program to find an element
// in an almost sorted array
using System;
 
class GFG
{
    // A recursive binary search based function.
    // It returns index of x in given array
    // arr[l..r] is present, otherwise -1
    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;
    }
 
    // Driver code
    public static void Main()
    {
        GFG ob = new GFG();
        int []arr = {3, 2, 10, 4, 40};
        int n = arr.Length;
        int x = 4;
        int result = ob.binarySearch(arr, 0, n - 1, x);
        if(result == -1)
            Console.Write("Element is not present in array");
        else
            Console.Write("Element is present at index " +
                           result);
    }
}
 
// This code is contributed by nitin mittal.

<?php
// PHP program to find an element
// in an almost sorted array
 
// A recursive binary search based function.
// It returns index of x in given array
// arr[l..r] is present, otherwise -1
function binarySearch($arr, $l, $r, $x)
{
    if ($r >= $l)
    {
        $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;
}
 
// Driver Code
$arr = array(3, 2, 10, 4, 40);
$n = sizeof($arr);
$x = 4;
$result = binarySearch($arr, 0, $n - 1, $x);
if($result == -1)
    echo("Element is not present in array");
else
    echo("Element is present at index $result");
 
//This code is contributed by nitin mittal
?>

<script>
// Javascript program to find an element
// in an almost sorted array
 
// A recursive binary search based function.
    // It returns index of x in given array
    // arr[l..r] is present, otherwise -1
function binarySearch(arr,l,r,x)
{
    if (r >= l)
        {
            let mid = l + Math.floor((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;
}
 
// Driver code
let arr=[3, 2, 10, 4, 40];
let n = arr.length;
let x = 4;
let result = binarySearch(arr, 0, n - 1, x);
if(result == -1)
    document.write("Element is not present in array<br>");
else
    document.write("Element is present at index " +
                   result+"<br>");
 
 
// This code is contributed by unknown2108
</script>