Search in Rotated Sorted Array Leetcode

Question

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;
    }
};

Binary search can only be used with sorted arrays. (when applying to arrays) — MikeCAT
– MikeCAT, Commented Jun 18, 2021 at 11:48
When you call bin_search recursively, what are you doing with the the result those calls returns? — Some programmer dude
– Some programmer dude, Commented Jun 18, 2021 at 11:52
@Someprogrammerdude oh thanks m=bin_search(nums,target,l,m) should be there in the code. — anfjnlnl
– anfjnlnl, Commented Jun 18, 2021 at 11:59
Note that calling bin_search() inside bin_search() and throwing the resulting value away makes no sense. — Evg
– Evg, Commented Jun 18, 2021 at 13:09

anirudh · Accepted Answer · 2021-06-18 11:59:16Z

1

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)

edited Jun 18, 2021 at 11:59

answered Jun 18, 2021 at 11:51

anirudh

1,4967 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

anfjnlnl Over a year ago

I think I'm doing that can you confirm?

anirudh Over a year ago

@anfjnlnl if you have any more concerns do let me know!

Evg Over a year ago

Strictly speaking, not only for sorted arrays. Take a look at std::binary_search() algorithm requirements.

Collectives™ on Stack Overflow

Search in Rotated Sorted Array Leetcode

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related