在旋转排序数组中搜索 Leetcode

Question

我卡在 question 了。我的代码不断返回 3 作为输入 nums = [4,5,6,7,0,1,2], target = 0 的输出。我正在做二进制搜索的一些修改版本并打印中间索引的索引并检查该索引处的值是否等于二进制搜索中中间索引的目标 value.Values 是 stdout:3 5 4 但不是返回4我的程序returns3。你能告诉我我的逻辑哪里不对吗？

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

Answer 1

您必须考虑对二分搜索方法进行一些修改，因为二分搜索方法仅适用于排序数组。

提示：考虑找到一些子数组（已排序），然后仅对这些特定部分应用二进制搜索。

目前，您没有比较 a[low] & a[mid]。只有比较这两个数组索引，您才能了解数组元素在子数组中的情况（增加或减少）。

您正在将 a[low] & a[mid] 与您的 target element 进行比较，这不会输出所需的子数组关系（增加或减少）

在旋转排序数组中搜索 Leetcode

Search in Rotated Sorted Array Leetcode

c++

arrays

binary-search