Finding Number
PROBLEM :
An array is bitonic if it is comprises of an increasing sequence of integers followed immediately by a decreasing sequence of integers.
Given such a array, you need to find a element X in it and print its index.
In case, X does not exist in the array print "OOPS! NOT FOUND" without quotes.
Note: It is guaranteed that array consist of distinct elements. And array indexing is from 0.
Input:
First line will consist a number T, the number of test cases.
Each test case will then consist of two numbers N and X. N being the array size and X being the element to be searched for.
Next line will consist of N space separated integers.
Output:
Print the required answer on separate lines.
Constraints:
1<=T<=10
1<=N<=200
-100<=A[i]<=100
Example:
INPUT
1
5 2
1 2 7 4 3
OUTPUT
1
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------
#include<iostream>
using namespace std;
int FindingNumber(int [],int ,int ) ;
int FindPivot(int [],int ,int ) ;
int FindNumber(int [],int ,int ,int ) ;
int main()
{
int t ;
cin>>t ;
while(t--)
{
int no,k ;
cin>>no>>k ;
int arr[no] ;
for(int i=0;i<no;i++)
cin>>arr[i] ;
no=FindingNumber(arr,no,k) ;
if(no==-1)
cout<<"OOPS! NOT FOUND" ;
else
cout<<no ;
cout<<endl ;
}
return 0;
}
int FindingNumber(int arr[],int no,int k)
{
int pivot=FindPivot(arr,0,no-1) ;
if(pivot==-1)
return FindNumber(arr,0,no-1,k) ;
if(arr[pivot]==k)
return pivot ;
if(arr[0]<=k)
return FindNumber(arr,0,pivot-1,k) ;
else
return FindNumber(arr,pivot+1,no-1,k) ;
}
int FindPivot(int arr[],int start,int end)
{
if(start>end)
return -1 ;
if(start==end)
return start ;
int mid=(start+end)/2 ;
if(mid<end&&arr[mid]>arr[mid+1])
return mid ;
else if(mid>start&&arr[mid]<arr[mid-1])
return mid-1 ;
else if(arr[start]>=arr[mid])
return FindPivot(arr,start,mid-1) ;
else
return FindPivot(arr,mid+1,end) ;
}
int FindNumber(int arr[],int start,int end,int k)
{
if(start>end)
return -1 ;
int mid=(start+end)/2 ;
if(arr[mid]==k)
return mid ;
else if(arr[mid]<k)
return FindNumber(arr,mid+1,end,k) ;
else
return FindNumber(arr,start,mid-1,k) ;
}
--------------------------------------------------------------------------------
An array is bitonic if it is comprises of an increasing sequence of integers followed immediately by a decreasing sequence of integers.
Given such a array, you need to find a element X in it and print its index.
In case, X does not exist in the array print "OOPS! NOT FOUND" without quotes.
Note: It is guaranteed that array consist of distinct elements. And array indexing is from 0.
Input:
First line will consist a number T, the number of test cases.
Each test case will then consist of two numbers N and X. N being the array size and X being the element to be searched for.
Next line will consist of N space separated integers.
Output:
Print the required answer on separate lines.
Constraints:
1<=T<=10
1<=N<=200
-100<=A[i]<=100
Example:
INPUT
1
5 2
1 2 7 4 3
OUTPUT
1
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------
#include<iostream>
using namespace std;
int FindingNumber(int [],int ,int ) ;
int FindPivot(int [],int ,int ) ;
int FindNumber(int [],int ,int ,int ) ;
int main()
{
int t ;
cin>>t ;
while(t--)
{
int no,k ;
cin>>no>>k ;
int arr[no] ;
for(int i=0;i<no;i++)
cin>>arr[i] ;
no=FindingNumber(arr,no,k) ;
if(no==-1)
cout<<"OOPS! NOT FOUND" ;
else
cout<<no ;
cout<<endl ;
}
return 0;
}
int FindingNumber(int arr[],int no,int k)
{
int pivot=FindPivot(arr,0,no-1) ;
if(pivot==-1)
return FindNumber(arr,0,no-1,k) ;
if(arr[pivot]==k)
return pivot ;
if(arr[0]<=k)
return FindNumber(arr,0,pivot-1,k) ;
else
return FindNumber(arr,pivot+1,no-1,k) ;
}
int FindPivot(int arr[],int start,int end)
{
if(start>end)
return -1 ;
if(start==end)
return start ;
int mid=(start+end)/2 ;
if(mid<end&&arr[mid]>arr[mid+1])
return mid ;
else if(mid>start&&arr[mid]<arr[mid-1])
return mid-1 ;
else if(arr[start]>=arr[mid])
return FindPivot(arr,start,mid-1) ;
else
return FindPivot(arr,mid+1,end) ;
}
int FindNumber(int arr[],int start,int end,int k)
{
if(start>end)
return -1 ;
int mid=(start+end)/2 ;
if(arr[mid]==k)
return mid ;
else if(arr[mid]<k)
return FindNumber(arr,mid+1,end,k) ;
else
return FindNumber(arr,start,mid-1,k) ;
}
--------------------------------------------------------------------------------
Comments
Post a Comment