PROBLEM STATEMENT:
We are given a nearly sorted array, we have to search for an element in the array in logarithmic time. Here, nearly sorted array signifies that position of an element is at most one index left or right of the position it should be in a sorted array.
For example: 5 17 19 35 20 50
Sorted version is: 5 17 19 20 35 50 (20 and 35 are one index array from sorted position).
QUICK POINTS:
1. We will use modified binary search here.
ALGORITHM:
1. First, find the middle element.
2. If the middle element is equal to the element to be searched ( say x ), then return the index of the middle element.
3. If the previous element of middle element is equal to x, then return middle-1.
4. If the next element of middle element is equal to x, then return middle+1.
5. If the middle element is greater than x, then search in the left part starting from middle-2.
6. If the middle element is less than x, then search in the right part starting from middle+2.
CODE:
#include <bits/stdc++.h>
using namespace std;
int modbinsearch(int x,int l,int r,int a[],int n)
{
if(r>=l){
int middle=l+(r-l)/2;
if(x==a[middle])
return middle;
else if(x==a[middle-1] && middle-1>=0)
return middle-1;
else if(x==a[middle+1] && middle+1<n)
return middle+1;
else if(x>a[middle])
return modbinsearch(x,middle+2,r,a,n);
else if(x<a[middle])
return modbinsearch(x,l,middle-2,a,n);
}
return -1; //if the element doesn't exist
}
int main()
{
int n,x; //size of array
cin>>n>>x;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int ans=modbinsearch(x,0,n-1,a,n);
cout<<ans;
return 0;
}
INPUT
6 35
5 17 19 35 20 50
OUTPUT
3
0 Comments