Searching in a rotated sorted array

#1

The code is not working due to time limit exceeded problem. How can the code be optimised? The code is as follows-
#include
using namespace std;

int num_search(int a[],int start,int end,int key)
{
int mid,index=-1;
while(start<=end)
{
mid=(start+end)/2;
if(key==a[mid])
{
index=mid;
}
else if(a[start]>=a[mid])
{
if(key>=a[mid] && key<a[end])
num_search(a,mid+1,end,key);
else
num_search(a,start,mid-1,key);
}
else
{
if(key>=a[start] && key<a[mid])
num_search(a,start,mid-1,key);
else
num_search(a,mid+1,end,key);
}

}
return index;
}

int main() {
int i,n;
cin>>n;
int a[n];
for(i=0;i<n;i++)
{
cin>>a[i];
}
int key;
cin>>key;

cout<<num_search(a,0,n-1,key)<<endl;
return 0;
}

#2

Hi Megha, you need to work on your logic. The following is the hint:

  1. Find the pivot element i.e. the element whose next element to it is smaller than it.
  2. Divide the array into 2 subarrays at the pivot point.
  3. Call binary search on both the subarrays.

Reply to this thread in case of further queries.

#3

Thank you for the hint. I tried the pivot approach, but the time limit exceeded problem still persists in the following code:

#4

#include using namespace std; int pivotsearch(int arr[],int start,int end) { int mid=(start+end)/2; if(end<start) return -1; else if(end==start) return end; else if(start<mid && arr[mid]<arr[mid-1]) return mid-1; else if(end>mid && arr[mid]>arr[mid+1]) return mid; else if(arr[start]>=arr[mid]) return pivotsearch(arr,start,mid); else return pivotsearch(arr,mid+1,end); } int binsearch(int arr[],int start,int end,int key) { int pos=-1,mid; while(start<=end) { mid=(start+end)/2; if(key==arr[mid]) pos= mid; else if(key>arr[mid]) start= mid+1; else end= mid-1; } return pos; } int binpsearch(int arr[],int start, int end,int key) { int pivot=pivotsearch(arr,start,end); if(pivot==-1) return binsearch(arr,start,end,key); else{ if(key==arr[pivot]) return pivot; else if(key>=arr[start]) return binsearch(arr,start,pivot-1,key); else return binsearch(arr,pivot+1,end,key); } } int main() { int n,key; cin>>n; int arr[n]; for(int i=0;i<n;i++) { cin>>arr[i]; } cin>>key; cout<<binpsearch(arr,0,n-1,key); return 0; }

#5

Hey Megha, can you please copy your code on ide, save it and then share that link here, so that we can help you in debugging your code.

#6

Here is the link for the code:
https://ide.codingblocks.com/s/50924

#7

Hi Megha, add a break statement in the if block of the binsearch function at line number 29. If that still doesn’t work, please share the link of the question here as well.