-3

Consider Arr[5] = {4,5, 1,2,3}; Here array has two sorted subsets. One is {4,5} and other is {1,2,3}. I need to find an element X (any element) in the array with minimal time complexity.

P.S: I only need the logic for this problem. Thanks in advance.

Till now what I can think of is sorting the array with O(n*logn) time and search using binary search O(logn) time. But is there any other efficient logic of finding X?

helloworld
  • 3
  • 3
  • 3
    I think you have confused stackoverflow with a code writing service. Please provide a minimal, reproducible example: https://stackoverflow.com/help/minimal-reproducible-example – Rohit Kashyap Sep 30 '19 at 07:31
  • 2
    In *degenerated case* (all subsets of size `1`) you can have an *arbitrary array* and thus nothing better than looping over the array. – Dmitry Bychenko Sep 30 '19 at 08:15
  • What is the exact question? What have you tried? BTW, I liked your username :P – MayurK Sep 30 '19 at 09:51
  • 1
    *"The array can contain as many as sorted subsets (not limited) and the subset size can vary as well."*: this means you know *nothing* about the array. Every array with random numbers fits this description. – trincot Sep 30 '19 at 19:40
  • @DmitryBychenko I understand that issue, but can you suggest any solution for the above problem with array size 5 (subset size 2 and 3). For time being please assume that array contains all subsets of size 2 or more. – helloworld Oct 01 '19 at 06:20
  • @MayurK Thanks for asking. What I can think of is first sorting the array and then applying binary search. So total time complexity is O(n*logn) + O(logn) for sorting and searching the element. Can you any better way to search will less time complexity than that ? – helloworld Oct 01 '19 at 06:22
  • @trincot No I don't have the subset count and subset size (min and max) for the array. But I just want to first solve this problem with say 5 elements (2 subsets of size 2&3). Can you suggest anything ? Thanks. After I have the logic, I can think of solving bigger arrays with more subsets. I will modify the question. It is actually confusing. – helloworld Oct 01 '19 at 06:25
  • I have updated the question to a simple problem : array with 2 subsets of size 2 and 3. I am new to stack overflow. So please excuse any mistakes in writing/explaining the question. Thanks. – helloworld Oct 01 '19 at 06:30
  • When you array has a fixed size, then speaking of time complexity is irrelevant. If you are interested in time complexity you should not limit the array size. You'll have to scan the whole array. So linear time complexity. – trincot Oct 01 '19 at 06:44
  • BTW: the solution can be optimised if you have exactly two subsets like you now have in the question. But not when you know nothing about the array. – trincot Oct 01 '19 at 07:52
  • The answer is thus: just scan the array for value X. This has *O(n)* time complexity, which is of course better than sorting the array first. – trincot Oct 01 '19 at 07:55
  • @trincot Thanks for making your point clear. But can it be done less than O(n) time complexity? I mean, is there any method like binary search? I was asked this question in an interview, and both of the above answers were given by me. But I was asked to do it with lesser complexity. I still can't guess what answer would be perfect. – helloworld Oct 01 '19 at 08:28
  • If you don't know the number of sets, then (like I said before) you really know *nothing* about the data -- there is no difference is saying the array has random numbers. And if you know nothing about the data, there is no faster method to find a specific number, then to check every value until you find it. – trincot Oct 01 '19 at 09:35

1 Answers1

1

Complexity O(logN) by binary search


    int Arr[5]={4,5,1,2,3},l=0,r=4,mid,X,ans=-1;
    cin>>X;

Initialise the array Arr on which we are performing binary search.
X is the number we are trying to find , l=0 and r=sizeof(Arr)-1
ans is index of X, -1 if not present in array.

We have two condition when our given X will be in first half then we will update r to mid-1.

Case 1. Rotation point is in the first half and X also.
(Arr[l] > Arr[mid] && (X>=Arr[l] || X<=Arr[mid]))

It ensure that rotation point is in first half by Arr[l] > Arr[mid] and if X>=Arr[l] then X can only be in first half and X<=Arr[mid] then also X can only be in first half.

Case 2. Rotation point is in second half but X is in first half
(Arr[l]<=Arr[mid] && (X>=Arr[l] && X<=Arr[mid]))

If Arr[mid]==X then update answer and break loop.

    while(l<=r){
        cout<<l<<r<<" ";
        mid=(l+r)/2;
        if(Arr[mid]==X){
            ans=mid;
            break;
        }
        if((Arr[l] > Arr[mid] && (X>=Arr[l] || X<=Arr[mid])) 
           || (Arr[l]<=Arr[mid] && (X>=Arr[l] && X<=Arr[mid])))
            r=mid-1;
        else
            l=mid+1;
    }
    cout<<ans;
Arjun Singh
  • 387
  • 3
  • 9
  • 1
    https://stackoverflow.com/questions/4773807/searching-in-a-sorted-and-rotated-array Thanks Arjun. Hi All, Please refer the above link for more clarification. – helloworld Oct 17 '19 at 09:05