CODEWITHSUNDEEP
c++arraysbinary-search
anfjnlnl
anfjnlnl

Reputation: 65

Search in Rotated Sorted Array Leetcode

I'm stuck in the question. My code keeps returning 3 as output for the inputnums = [4,5,6,7,0,1,2], target = 0. I'm doing some modified version of binary search and printing the indices of middle index and checking whether value at that index is equal to the target value.Values of middle indices in binary search are stdout:3 5 4 but instead of returning 4 my program returns 3. Can you please tell me where my logic is incorrect?

class Solution {
public:
    int bin_search(vector<int>& nums,int target,int l,int r){
        int m;
        m=(r+l)/2;
        cout<<m<<" ";
        // if(r==l) break;
        if(nums[m]==target) return m;
        else if(r==l && nums[m]!=target) return -1;
        if(target>=nums[l] && target<=nums[m]){
            m=bin_search(nums,target,l,m);
        }
        else if(target>=nums[m+1] && target<=nums[r]){
            m=bin_search(nums,target,m+1,r);
        }
           
        
        // if(nums[m]==target) return m;
        return m;
    }
    
    int search(vector<int>& nums, int target) {
        int n=nums.size();
        int f;
        f=bin_search(nums,target,0,n-1);
        return f;
    }
};

Upvotes: 0

Views: 194

Answers (1)

anirudh
anirudh

Reputation: 1466

You'll have to think on some modification in the binary search approach because binary search approach is applicable only for sorted array.

Hint : Think about finding some subarrays (which are sorted) and then apply binary search only on those specific parts.

Currently, you are not comparing a[low] & a[mid]. Only if you compare these two array indices, you'll get an idea of how the array elements are in the subarray (increasing or decreasing).

You are comparing a[low] & a[mid] with your target element , which will not output the desired relation of subarray(increasing or decreasing)

Upvotes: 1

Related Questions