class Solution {
private:
int findpiv (vector<int>& nums, int l, int h) {
if (l > h) {
return -1;
}
if (l == h) {
return l;
}
int mid = (l+h)/2;
if (nums[mid-1] > nums[mid] && mid>l) {
return mid-1;
}
if (nums[mid] > nums[mid+1] && mid<h) {
return mid;
}
if (nums[l] > nums[mid]) {
return findpiv (nums, l, mid-1);
}
return findpiv (nums, mid+1, h);
}
int bsearch (vector<int>& nums, int target, int l, int h) {
if (l > h) {
return -1;
}
int mid = (l+h)/2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] > target) {
return bsearch (nums, target, l, mid-1);
}
return bsearch (nums, target, mid+1, h);
}
public:
int search(vector<int>& nums, int target) {
int piv = findpiv (nums, 0, nums.size()-1);
if (piv == -1) {
return bsearch (nums, target, 0, nums.size()-1);
}
if (target == nums[piv]) {
return piv;
}
if (target >= nums[0]) {
return bsearch (nums, target, 0, piv);
}
return bsearch (nums, target, piv, nums.size()-1);
}
};
For this question, this is the code I wrote. I'm getting an input array which is rotated and sorted. I first of all find out the pivot point of the array. And this is where I believe the error is arising.
I first felt that nums\[mid-1\]
would be giving me an error for mid == 0
. But, in that case, l == 0
. Hence mid\<l
won't satisfy, and it should not give me an error.
Maybe I'm mistaken in my concepts. Hence please guide me.