旋转数组的查找和最值

给定一个有序数组，如{1,2,3,4,5,6,7,8,9}，我们将对这个数组进行选择，位置旋转未知。下面给出一个可能的旋转结果。如{4,5,6,7,8,9,1,2,3}，我们可以理解为它从元素4位置开始旋转。之后给定一个指定的数字n，让我们从{4,5,6,7,8,9,1,2,3}这个数组中找出它的位置，要求时间复杂度尽可能的低。

观察数组可以得到的信息：

1.拐点的左右两边都是一个有序的数组。例如上面的拐点是9。

2.假设一个拐点，至少有一边是有序的。例如以7 为拐点，那么{4,5,6}是有序的。

以有序数组是递增的为例子

思路：

1.选择中间点middle作为拐点

2.a[middle] > a[low] middle左边数组是有序的

n<=a[middle]&&n>=a[low]，可以在左边数组查找。否则在右边数组查找

a[middle] < a[high] middle的右边数组是有序的

n>=a[middle]&&n<=a[high] , 可以在右边数组查找，否则在左边数组查找

（利用了一边有序的条件，让时间复杂度只需要O（lgn））

function find(x,arr) {
    let len=arr.length;
    let low=0,high=len-1;
    while (low<=high){
        let mid=Math.floor((low+high)/2);
        if(arr[mid]==x){
            return mid;
        }
        if(arr[mid]>arr[low]){
            if(arr[low]<=x && x<=arr[mid]){
                high=mid-1;
            }else {
                low=mid+1;
            }
        }else {
            if(arr[mid]<=x && x<=arr[high]){
                low=mid+1;
            }else {
                high=mid-1;
            }
        }
    }
    return -1;
}

查找最值：

function findMin(arr) {
    let len=arr.length;
    let low=0,high=len-1;
    while (low<high){
        let mid=Math.floor((low+high)/2);
        if(arr[low]<arr[mid]){
            low=mid+1;
        }
        if(arr[mid]<arr[low]){
            high=mid;
        }
    }
    return low;
}

最后

以上就是魁梧信封最近收集整理的关于旋转数组的查找和最值的全部内容，更多相关旋转数组内容请搜索靠谱客的其他文章。