I am doing a question related to binary search on leetcode and facing a run time error in it.
Can someone help me to solve the problem.
Problem link:
int binarySearch(vector<int> &arr,int n,int target,int low,int high)
{
int mid;
while(low<=high)
{
mid=low+ (high-low) /2;
if(arr[mid]==target)
return mid;
else if(target<arr[mid])
high=mid-1;
else
low=mid+1;
}
return -1;
}
int findPivot(vector<int> &arr,int n)
{
int low=0,high=n-1;
int mid;
while(low<=high)
{
mid=low+(-low+high)/2;
if(mid<high&&arr[mid]>arr[mid+1])
return mid;
if(mid>low&&arr[mid]<arr[mid-1])
return mid-1;
else{
if(arr[mid]>arr[low])
{
low=mid+1;
}
else
{
high=mid-1;
}
}
}
return -1;
}
class Solution {
public:
int search(vector<int>& arr, int target) {
int n=arr.size();
int pivot=findPivot(arr,n);
int ans=-1;
if(pivot==-1)
ans=binarySearch(arr,n,target,0,n-1);
if(arr[pivot]==target)
return -1;
else if(target<arr[0])
ans=binarySearch(arr,n,target,pivot+1,n-1);
else
ans=binarySearch(arr,n,target,0,pivot-1);
return ans;
}
};