DSA-Guide/Binary Search/Questions/Searching_Nearly_Sorted_Array.cpp at main · Kanav-Arora/DSA-Guide · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*
        Nearly Sorted Array is array in which ith element is on (i-1)th, ith, (i+1)th index
*/

#include<iostream>
using namespace std;

int NearlySorted(int arr[], int n, int target)
{
    int low =0;
    int high = n-1;
    int mid = low + (high-low)/2;

    while(low<high)
    {
        mid = low + (high-low)/2;

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

        else if(arr[mid-1]==target)
            return mid-1;

        else if(arr[mid+1]==target)
            return mid+1;

        else if(target>arr[mid] || target>arr[mid-1] || target>arr[mid+1])
            low = mid+2;

        else
            high = mid-2;
    }

    return -1;
}

int main()
{
    int arr[] = {5,10,30,20,40, 50, 80, 70, 90};
    cout<<NearlySorted(arr,9,70);
    return 0;
}