Search in an almost sorted array

Last Updated : 22 Oct, 2024

Given a sorted array arr[] of size n, some elements of array are moved to either of the adjacent positions, i.e., arr[i] may be present at arr[i+1] or arr[i-1] i.e. arr[i] can only be swapped with either arr[i+1] or arr[i-1]. The task is to search for an element in this array.

Examples :

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

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

Naive Approach – O(n) Time and O(1) Space

A simple solution is to linearly search the given key in array arr[].

C++

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

// Linear search function that returns the 
// index of x if found, otherwise -1
int linearSearch(const vector<int>& arr, int x) {
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == x) 
            return i; 
    }
    return -1; 
}

// Driver Code
int main() {
    vector<int> arr = { 3, 2, 10, 4, 40 };
    int x = 4;
    cout << linearSearch(arr, x);
    return 0;
}

Java

class Geeksforgeeks{
     public static int linearSearch(int arr[], int x)
    {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            if (arr[i] == x)
                return i;
        }
        return -1;
    }
      // Driver code
      public static void main(String args[])
    {
        int arr[] = { 3, 2, 10, 4, 40 };
        int x = 4;
 
        // Function call
        int result = linearSearch(arr, x);
        if (result == -1)
            System.out.print(
                "Element is not present in array");
        else
            System.out.print("Element is present at index "
                             + result);
    }
}
// This code is contributed by Vishal Dhaygude

Python

class Geeksforgeeks:
    @staticmethod
    def linearSearch(arr, x):
        n = len(arr)
        for i in range(n):
            if arr[i] == x:
                return i
        return -1
      
# Driver code
if __name__ == '__main__':
    arr = [3, 2, 10, 4, 40]
    x = 4

    # Function call
    result = Geeksforgeeks.linearSearch(arr, x)
    if result == -1:
        print("Element is not present in array")
    else:
        print("Element is present at index", result)

using System;

class Geeksforgeeks {
    public static int LinearSearch(int[] arr, int x)
    {
        int n = arr.Length;
        for (int i = 0; i < n; i++) {
            if (arr[i] == x)
                return i;
        }
        return -1;
    }

    // Driver code
    static void Main(string[] args)
    {
        int[] arr = { 3, 2, 10, 4, 40 };
        int x = 4;

        // Function call
        int result = LinearSearch(arr, x);
        if (result == -1)
            Console.WriteLine(
                "Element is not present in array");
        else
            Console.WriteLine("Element is present at index "
                              + result);
    }
}
// This code is contributed by Prajwal Kandekar

JavaScript

// Javascript Equivalent

function linearSearch(arr, x) {
    let n = arr.length;
    for (let i = 0; i < n; i++) {
        if (arr[i] == x)
            return i;
    }
    return -1;
}

// Driver code
let arr = [3, 2, 10, 4, 40];
let x = 4;

// Function call
let result = linearSearch(arr, x);
if (result == -1)
    console.log("Element is not present in array");
else
    console.log("Element is present at index " + result);

Output

Using Binary Search – O(Log n) Time and O(1) Space

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.

Follow the steps below to implement the idea:

Initialize a variable mid with l+(r-l)/2.
If arr[mid] is equal to x return mid
Else if arr[mid-1] is equal to x return mid-1
Else if arr[mid+1] is equal to x return mid+1
If arr[mid] > x recur for search space l to mid-2 else recur for search space mid+2 to r.

C++

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

// An iterative binary search function.
// It returns the index of x in the given array
// arr[l..r] if present, otherwise -1
int binarySearch(const vector<int>& arr, int x) {
    int l = 0, r = arr.size() - 1;

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

        // Check 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;

        // Search in left subarray
        if (arr[mid] > x) 
            r = mid - 2;
        // Search in right subarray
        else 
            l = mid + 2;
    }
    return -1; // Element not found
}

// Driver Code
int main() {
    vector<int> arr = { 3, 2, 10, 4, 40 };
    int x = 4;
    cout << binarySearch(arr, x);
    return 0;
}

Java

// Java program to find an element
// in an almost sorted array
import java.io.*;

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

# 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.

JavaScript

<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>

PHP

<?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
?>