leetcode question 81 c++ returns wrong answer

Question

question: There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

You must decrease the overall operation steps as much as possible.

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int s=0;
        vector<int> f(4999);
        vector<int> x(4999);
        int y=f.size()-1;
        int z=x.size()-1;
        for (int i=0;i<nums.size();i++){
           for (int j=1;j<nums.size();j++){
               if (i<=j){
                   f.push_back(nums[i]);
               }else if (i>j){
                   f.push_back(nums[i]);
                   x.push_back(nums[j]);
                   for (int k=j;k<nums.size();k++)
                       x.push_back(nums[k]);
                   break;
               }
           } 
        }
        if (target==x[0]||target==f[0]){
            return true;
        }
        else if (target>f[0]){
            while (s<=y){
                int mid=0;
                mid=(y+s)/2;
                if (f[mid]>target){
                    y=mid-1;
                }else if (f[mid]<target){
                    s=mid+1;
                }else if (f[mid]==target){
                    return true;
                }
            }
            return false;
        }else if (target<f[0]){
            while (s<=z){
                int mid=0;
                mid=(z+s)/2;
                if (x[mid]>target){
                    z=mid-1;
                }else if (x[mid]<target){
                    s=mid+1;
                }else if (x[mid]==target){
                    return true;
                }
            }
            return false;
        }
        else{
            return false;
        }return false;
    }
};

input [2,5,6,0,0,1,2] target 2 returned false expected true
input [1] target 1 returned false expected true
input [1] target 0 returned true expected false

trying to stick to a binary search solution how can this work help is appriciated thanks

score 0 · Accepted Answer · answered Oct 07 '22 at 05:29

To figure out why it's not working, you can walk through one of the failing test cases. You'd want to pick the easiest one to manage in your head, so in this case I recommend one of those with an array length of 1.

So let's walk through

input [1] target 1 returned false expected true

Your function first creates two large arrays, each with 4999 zeros in them. See this answer for why they're zero.

Then that nested for loop runs, but it doesn't actually do anything because the inner loop will not run -- j=1 is not less than nums.size(), which is 1.

So by the time you do your binary searches below, both f and x are filled with 4999 zeros. Your code does the binary search on f, so it won't find your target of 1.

If you want to see the solution to this problem, check out this Stack Overflow answer.

leetcode question 81 c++ returns wrong answer

1 Answers1