欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

在一个有序的旋转数组中,查找给定值

程序员文章站 2022-05-18 17:16:50
...

思路一:

因为数组有序,经过旋转后,数组保持局部有序。因此可以用二分查找。

bool search(int A[], int n, int target) {
       int start=0;
       int end=n-1;
        while(start<=end){
            int mid=(start+end)>>1;
            if(target==A[mid])
                return true;
            if(A[mid]==A[start]&&A[mid]==A[end]){   //此时给定值可能在左边,也可能在右边。因此要遍历整个数组。  或者++start,--last.
                /*
                for(int i=0;i<n;i++){
                    if(target==A[i])
                        return true;
                }
                return false;*/
                start++;
                end--;
            }else if(A[start]<=A[mid]){    //左边有序
                 if(target<A[mid]&&target>=A[start])
                    end=mid-1;
                else
                    start=mid+1;
            }else if(A[mid]<=A[end]){      //右边有序
                if(target>A[mid]&&target<=A[end])
                    start=mid+1;
                else
                    end=mid-1;
            }
        }
        return false;
    }


推荐阅读