0

In this code I am taking an sorted array that is circularly shifted k position as an input and I need to find the largest element in the array in O(log n) so I used the logic as such that if the element at 0 index in sorted array is same as circularly array then return the value of position for the same I used binary search but I am getting -1 from the function

Here is the code:

#include<iostream>
#include<algorithm>
using namespace std;
int position(int ar[],int start,int end,int item ){
    int mid;  
    if(end >= start)   
    {     
        mid = (start + end)/2;  
        if(ar[mid] == item)  
        {  
            return mid+1; 
        }  
        else if(ar[mid] < item)   
        {  
            return position(ar,mid+1,end,item);  
        }  
        else   
        {  
            return position(ar,start,mid-1,item);  
        }    
    }  

} 
int main(){
    int l,e=0,pos=0,k=0,lar=0;
    cout<<endl<<"Enter the length of the array = ";
    cin>>l;
    int arr[l],temp[l];
    cout<<endl<<"Enter the array elements:-"<<endl;
    for(int i=0;i<l;i++){
        cout<<"Enter the element at "<<(i+1)<<" = ";
        cin>>arr[i];
        temp[i]=arr[i];
    }
    sort(temp,temp+l);
    e=temp[0];
    k=position(arr,0,l,e);
    lar=arr[k-1];
    cout<<endl<<"Value of k = "<<k<<endl;
    cout<<endl<<"largest element in the array is "<<lar<<endl;
    return 0;
}
soma
  • 53
  • 5
  • https://en.cppreference.com/w/cpp/algorithm/nth_element – Jesper Juhl Oct 02 '21 at 18:35
  • Your code has issues that your compiler should inform you of. Please [enable warnings](https://stackoverflow.com/questions/57842756/why-should-i-always-enable-compiler-warnings) and address them, then use the cleaned-up code in your question. – JaMiT Oct 02 '21 at 20:14
  • 1
    Your explanation of your algorithm is unclear, in part because of your disdain for punctuation. – Beta Oct 02 '21 at 20:15
  • Sorting an array takes `O(n log n)` time. So if sorting is a part of your algorithm, it's already in violation of `O(log n)` requirement. – Igor Tandetnik Oct 02 '21 at 23:01
  • Since you pass the smallest element in the array as `item`, `ar[mid] < item` condition can't possibly be true. So the binary search would always go left, never right. That seems wrong, as a shifted array may certainly have its smallest element in its right half. – Igor Tandetnik Oct 02 '21 at 23:03

1 Answers1

0

Let's talk about your approach first.

I need to find the largest element in the array

In your code, you're sorting the array in increasing order.

Then you're trying to find the position of first value of the array, which is smallest one.

e=temp[0];
k=position(arr,0,l,e);

Here you need to set e as the last value of the temp array, because largest value is at the end of the array. Then send that to position function.

Another thing, you're sorting the temp array. Which is taking nLogn time itself.

Let's talk about possible solution approach:

Approach 1

A simple solution is to traverse the complete array and find maximum. This solution requires O(n) time.

Approach 2 (using binary search)

In a sorted array (even rotated), you can use just only binary search to find the largest number, which will take O(Logn) time.

All you've to do is check some additional things.

Here's a sample code:

int _getMaxValue(int ar[], int arLen)
{
    for(int i = 0; i<=arLen ; i++) cout<<i<<" "<<ar[i]<<endl;

    int left = 0, right = arLen;
    while(left < right)
    {
        int mid = left + (right - left) / 2;

        if(ar[left] == ar[mid]) break;
        else if(ar[left] < ar[mid])
        {
            /**
            consider 2 cases
             1. 5 6 7 1 2 -> 1 2 5 6 7
             2. 2 1 7 6 5 -> 7 6 5 2 1
            */
            if(ar[right] < ar[left]) right = mid;
            else left = mid;    // case 2
        }
        else
        {
            /**
            consider 2 cases
             1. 5 6 1 2 3 -> 1 2 3 5 6
             2. 3 2 1 6 5 -> 6 5 3 2 1
            */
            if(ar[right] < ar[left]) right = mid;   // for case 1
            else left = mid;    // case 2
        }
    }
    return ar[left] > ar[right] ? ar[left] : ar[right];
}

You can reduce the above code like below:

int _getMaxValue(int ar[], int arLen)
{
    int left = 0, right = arLen;
    while(left < right)
    {
        int mid = left + (right - left) / 2;

        if(ar[left] == ar[mid]) break;

        if(ar[right] < ar[left]) right = mid;
        else left = mid;
    }
    return ar[left] > ar[right] ? ar[left] : ar[right];
}

Main function

int main()
{
    int l,e=0,pos=0,k=0,lar=0;
    cout<<endl<<"Enter the length of the array = ";
    cin>>l;
    int arr[l];
    cout<<endl<<"Enter the array elements:-"<<endl;
    for(int i=0; i<l; i++)
    {
        cin>>arr[i];
    }

    int mx = _getMaxValue2(arr, l-1);
    cout<<"maximum num: "<<mx<<endl;
    return 0;
}
Md. Faisal Habib
  • 1,014
  • 1
  • 6
  • 14