THIS CODE IS FIND ELEMENT IN ROTATION ARRAY
user_6075971
plain_text
3 years ago
1.5 kB
8
Indexable
#include <iostream>
using namespace std;
//THIS CODE IS FIND ELEMENT IN ROTATION ARRAY
// THIS CODE USE ONLY ROTION ARRAY
int pivot(int arr[], int n)
{
int s = 0;
int e = n - 1;
int mid = (s + e) / 2;
while (s < e)
{
if (arr[0] < arr[mid])
{
s = mid + 1;
}
else
{
e = mid;
}
mid = (s + e) / 2;
}
return e;
}
int binary_serch(int arr[], int n, int k, int s, int e)
{
//int s = pivot;
// int e = n - 1;
int mid = (s + e) / 2;
while (s < e)
{
if (arr[mid] == k)
{
return mid;
}
else if (arr[mid] < k)
{
s = mid + 1;
}
else
{
e = mid - 1;
}
mid = (s + e) / 2;
}
}
int main()
{
int arr[100];
int n;
cout << "ENTER THE ARRAY SIZE--->";
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
cout << "YOUR PIVOT IS--->" << pivot(arr, n);
cout<<endl;
int k;
cout << "ENTER THE KEY--->";
cin >> k;
int z = pivot(arr, n);
if (arr[z] <= k && k <= arr[n - 1])
{
cout <<"YOUR INDEX IS--->"<< binary_serch(arr, n, k, z, n - 1);
}
else
{
cout <<"YOUR INDEX IS--->"<< binary_serch(arr, n, k, 0, z);
}
return 0;
}Editor is loading...