Open In App

Search in an almost sorted array

Last Updated : 07 Mar, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

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}, key = 40
Output:
Explanation: Output is index of 40 in given array i.e. 2

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

Naive Approach:

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

Below is implementation of the above approach:

C++




#include<bits/stdc++.h>
using namespace std;
 
int linearSearch(int arr[], int n, int x)
{
    int i;
    for (i = 0; i < n; i++)
        if (arr[i] == x)
            return i;
    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 = linearSearch(arr, n, x);
    (result == -1)
        ? printf("Element is not present in array")
        : printf("Element is present at index %d", result);
    return 0;
}
 
// This code is contributed by Vishal Dhaygude


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


Python3




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)


C#




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

Element is present at index 3

Time complexity: O(N). 
Auxiliary Space: O(1)

We can modify binary search to do it in O(Logn) time. 

Search in an almost sorted array using Binary search:

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:

  • Construct a recursive function to search for that takes array arr[], left pointer l and right pointer r as input and returns the index of x in array. 
    • 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.

Below is the implementation of this approach.

C++




// C++ program to find an element
// in an almost sorted array
#include <bits/stdc++.h>
using namespace std;
 
// 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




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


Python3




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




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


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>


Output

Element is present at index 3

Time complexity: O(Logn).
Auxiliary Space: O(1)

 



Previous Article
Next Article

Similar Reads

Sort an almost sorted array where only two elements are swapped
Given an almost sorted array where only two elements are swapped, how to sort the array efficiently?Examples : Input: arr[] = {10, 20, 60, 40, 50, 30} // 30 and 60 are swapped Output: arr[] = {10, 20, 30, 40, 50, 60} Input: arr[] = {10, 20, 40, 30, 50, 60} // 30 and 40 are swapped Output: arr[] = {10, 20, 30, 40, 50, 60} Input: arr[] = {1, 5, 3} //
7 min read
Check if given array is almost sorted (elements are at-most one position away)
Given an array with n distinct elements. An array is said to be almost sorted (non-decreasing) if any of its elements can occur at a maximum of 1 distance away from their original places in the sorted array. We need to find whether the given array is almost sorted or not.Examples: Input : arr[] = {1, 3, 2, 4}Output : YesExplanation : All elements a
11 min read
Find count of Almost Prime numbers from 1 to N
Given a number N. Find number of almost primes from 1 to [Tex]n [/Tex]. A number is called almost if it has exactly two distinct prime factors. Note: The numbers can have any number of non-prime factors but should have exactly two prime factors.Examples: Input : N = 10 Output : 2 Explanation : 6, 10 are such numbers. Input : N = 21 Output : 8 An ef
10 min read
Split a Circular Linked List into three halves of almost same size
Split given Circular Linked List into three halves without calculating its length such that the difference between a linked list with a maximum number of nodes and a linked list with a minimum number of nodes is minimum. Examples: Input: Circular Linked List: 1-&gt;3-&gt;5-&gt;7-&gt;9Output: 1 3 5 7 9 Input: Circular Linked List: 2-&gt;4-&gt;8Outpu
10 min read
Proof that Almost-SAT is NP Complete
Prerequisite: NP-Completeness, NP Class, SAT Problem- The Almost-SAT problem which is built on top of SAT(Boolean Satisfiability Problem) problem takes a boolean formula in conjunctive normal form with m clauses as input. If such an assignment exists, the result is an assignment of the literals such that exactly m-1 clauses evaluate to TRUE, otherw
5 min read
Almost Prime Numbers
AA k-Almost Prime Number is a number having exactly k prime factors (not necessarily distinct). For example, 2, 3, 5, 7, 11 ....(in fact all prime numbers) are 1-Almost Prime Numbers as they have only 1 prime factor (which is themselves). 4, 6, 9.... are 2-Almost Prime Numbers as they have exactly 2 prime factors (4 = 2*2, 6 = 2*3, 9 = 3*3) Similar
9 min read
Almost Perfect Number
Given a number n, check it is the Almost Perfect number or not. Almost perfect number is a natural number whose sum of all divisors including 1 and the number itself is equal to 2n - 1.Example : Input: n = 16Output: YesExplanation: sum of divisors = 1 + 2 + 4 + 8 + 16 = 31 = 2n - 1 Input: n = 9Output: NoExplanation: sum of divisors = 1 + 3 + 9 ? 2n
4 min read
Count number of common elements between a sorted array and a reverse sorted array
Given two arrays consisting of N distinct integers such that the array A[] and B[] are sorted in ascending and descending order respectively, the task is to find the number of values common in both arrays. Examples: Input: A[] = {1, 10, 100}, B[] = {200, 20, 2}Output: 0 Input: A[] = {2, 4, 5, 8, 12, 13, 17, 18, 20, 22, 309, 999}, B[] = {109, 99, 68
15+ min read
Circularly Sorted Array (Sorted and Rotated Array)
Circularly sorted arrays are arrays that are sorted in ascending or descending order and then rotated by a number of steps. Let us take an example to know more about circularly sorted arrays: Consider an array: arr[] = {23, 34, 45, 12, 17, 19}The elements here, {12, 17, 19, 23, 34, 45} are sorted 'In-order' but they are rotated to the left by 3 tim
7 min read
Check if two sorted arrays can be merged to form a sorted array with no adjacent pair from the same array
Given two sorted arrays A[] and B[] of size N, the task is to check if it is possible to merge two given sorted arrays into a new sorted array such that no two consecutive elements are from the same array. Examples: Input: A[] = {3, 5, 8}, B[] = {2, 4, 6}Output: Yes Explanation: Merged array = {B[0], A[0], B[1], A[1], B[2], A[2]} Since the resultan
15+ min read
Article Tags :
Practice Tags :
three90RightbarBannerImg