题目描述

假设有一个数列，它是一个有序数列围绕某个点旋转得到的。要求写算法在该数列中查找某给定数，看是否存在，存在则返回其位置。

题解

暴力解法：

直接从前到后扫描整个数组，时间复杂度最优O(1)，最坏O(n)。

public static int bfSearch(int[]arr,int target){
    for(int i=0;i<arr.length;i++){
        if(arr[i]==target){
            return i;
        }
    }
    return -1;
}

利用有序性的变形二分查找法：

利用数组的有序性，可以想到二分查找，但由于原来有序的数组绕某个点旋转过，因此需要对二分查找进行变形。

class Solution {
    public int search(int[] nums, int target) {
        return binarySearchRecursion(nums,target,0,nums.length-1);
    }
    private int binarySearchRecursion(int[]arr,int target,int begin,int end){
        if(end < begin){
            return -1;
        }
        int mid = (begin+end)/2;
        if(arr[mid]==target){
            return mid;
        }else if(arr[0]<=arr[mid]){//mid的左边未旋转，优先处理左边
            if(target>=arr[0]&&target<arr[mid]){
                return binarySearchRecursion(arr,target,begin,mid-1);
            }else{
                return binarySearchRecursion(arr,target,mid+1,end);
            }
        }else{//mid的左边跨越两段,可以说明mid右边未旋转，优先处理右边
            if(target>arr[mid]&&target<=arr[arr.length-1]){
                return binarySearchRecursion(arr,target,mid+1,end);
            }else{
                return binarySearchRecursion(arr,target,begin,mid-1);
            }
        }
    }
}

时间复杂度为O(logn)。

寻找有序数组旋转后的某个元素

原文：https://www.cnblogs.com/hickey2048/p/14604779.html