edited by
1,146 views
1 votes
1 votes

Consider an array contain n distinct elements. In array till ‘i’ location element are in increasing order and after ‘i’ location all elements are in decreasing order. What is the time complexity to find location of ith element?

edited by

2 Answers

Best answer
4 votes
4 votes

#include <stdio.h>

int main()
{
    int a[]={6,9,5,3,3,2,0,0,-1,-4};
     
    int low=0,high=10;
  int i= findarray(a,low,high);
  printf("%d\n",i);
    return 0;
}
int findarray(int *p,int b,int c)
{
    int mid=(b+c)/2;
    if(p[mid-1]<p[mid])
     {
         if(p[mid]<p[mid+1])
           return findarray(p,mid+1,c);
         else return mid;  
     }
     else return findarray(p,b,mid);

}
 

This is the programme to find the ith element position and it finds with in a time complexity of O(logn)

For the above input it returns '1' as value .

selected by
3 votes
3 votes

We can do it by binary search

  • Firstly put binary search in the array
  • Middle element of array is found , then search a[mid]<a[mid+1] and a[mid+1]>a[mid+2]
  • If this condition satisfies, then exit
  • Otherwise if a[mid+1]<a[mid+2] , do a[first]=a[mid+1]
  • Otherwise if a[mid]>a[mid+1], then a[last]=a[mid+1]

So, O(logn) time sufficient for it

Related questions

1 votes
1 votes
1 answer
2
2 votes
2 votes
0 answers
3
3 votes
3 votes
0 answers
4
aaru14 asked Nov 23, 2017
444 views
https://gateoverflow.in/?qa=blob&qa_blobid=6856287731579574233someone plz tell ??