Question:-  How to find an element in rotated sorted array?
Input 1: array[]={4,5,6,7,8,9,1,2,3}; element=5 Output : position of the element(=5) is 1 (array starts from zero). Input 2: array[]={1,2,3,4,5,6,7,8,9}; element=7 Output : position of the element(=7) is 6 (array starts from zero). The below mentioned code has been compiled in Microsoft Visual Studio 6.0 #include<stdio.h> int find_element_position(int *a, int first , int last , int element); main() { int a[10]={3,4,5,6,7,8,9,1,2}; int pos; int element; printf("Give the element\n"); scanf("%d",&element); pos=find_element_position(a,0,8 ,element); printf("The smallest element=%d position is %d\n",element , pos); } int find_element_position(int *a, int first , int last , int element) { int mid; int pos = -1; while(first<last-1) { mid=(first+last)/2; if(a[mid]==element) { first=mid; break; } if(a[first]<a[mid]) { if(element >= a[first] && element < a[mid]) { last = mid-1; } else { first = mid; } } else { if(element >=a[mid] && element <= a[last]) { first = mid; } else { last = mid-1; } } } if(a[first]==element) pos=first; if(a[last]==element) pos=last; return pos; }

NB:

The above question is one of the Frequently asked question in software Job interview in BIG company.
Free Web Hosting