PROBLEM STATEMENT:
We are given an infinite sorted array, where the array has infinite number of elements. We have to find the position of a given element in the array.
QUICK POINTS:
We have to modify the binary search algorithm to solve this problem as it has infinite end index which is inconvenient to normal binary search. We can apply binary search with modification here because the array is sorted.
This problem is not a problem that can take user input because the array is infinite. So, there must be some conditions that defines the array.
Here, we are taking the array as all the natural numbers.
ALGORITHM:
1. First we have to determine a segment that contains the element to be located starting from initial index.
2. Let's take low index=0, and high index=1, and i=2 i.e. the maximum element that is present in this range. Now, we will check if the given element is present in this range i.e if i>x ( x is the given element). If i<x, then we will continue the loop making low=previous value of high and high will be doubled i.e. high=2*high (previous) and i will be incremented to high+1.
3. Thus, we can determine a finite segment with low and high value that contains the given element. Now, we will apply binary search in this range.
4. Find the middle index of the list.
5. Compare x with (middle index +1) (for natural number, element=index+1). If x is equal to the middle+1, then we return the middle index as the position of x.
If x is greater than middle+1, then x will lie in the right part of the middle index, and we will consider the right part as our list for next step.
If x is less than the middle+1 , then x will lie in the left part of the middle index, and we will consider the left part as our list for next step.
3. The same steps are continued until we find a list consisting of only one element and that is equal to x.
CODE:
#include <bits/stdc++.h>
using namespace std;
int binsearch(int x,int l,int r)
{
if(r>=l){
int middle=l+(r-l)/2;
if(x==middle+1)
return middle;
else if(x>middle+1)
return binsearch(x,middle+1,r);
else if(x<middle+1)
return binsearch(x,l,middle-1);
}
return -1; //if the element doesn't exist
}
int main()
{
int x;
cin>>x;
int low=0, high=1,i=2;
while(x>i)
{
low=high;
high=2*high;
i=high+1;
}
int ans=binsearch(x,low,high);
cout<<ans;
return 0;
}
INPUT:
50
OUTPUT:
49
0 Comments