Find element in rotation array

 avatar
user_6075971
plain_text
2 years ago
1.5 kB
0
Indexable
Never
#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;
}