美文网首页
旋转数组的任意元素(二分法)

旋转数组的任意元素(二分法)

作者: 掌灬纹 | 来源:发表于2019-01-28 20:31 被阅读0次

    描述

    输入一个递增排序的数组(元素不重复)的一个旋转(次数不详),找出某个元素.复杂度 O(lgn)。

    输入

    第一行:N,数组的长度

    第二行:N个整数,作为数组的元素,空格分开

    第三行:要查找的关键字K

    输出

    关键字K的下标,如果没有找到,输出-1

    样例输入

    5

    6 1 2 3 4

    1

    样例输出

    1

    思路:

    巧用二分法解题,可以先找出旋转数组最小值(前边详细解释过),然后以最小值为轴,左右一定分别有序,在比较目标与数组尾元素的大小,判断在左还是右进行二分查找。

    (Java代码参考如下)

    import java.util.Scanner;

    public class Exam11_FindInRotaryArr {

    public static void main(String[] args) {

    int res = 0;

    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();

    int[] a = new int[n];

    for(int i = 0; i < a.length; i++) {

    a[i] = sc.nextInt();

    }

    int target = sc.nextInt();

    if(target == a[minIndex(a)]) {

    res = minIndex(a);

    }else if(target > a[a.length-1]) {//在最小数左侧做二分查找

    res = binarySearch(a, 0, minIndex(a)-1, target);

    }else if(target < a[a.length-1]) {//在最小数右侧做二分查找

    res = binarySearch(a, minIndex(a)+1, a.length-1, target);

    }

    System.out.println(res);

    }

    static int minIndex(int[] arr) {

    int begin = 0;

    int end = arr.length - 1;

    if(arr[begin] <= arr[end]) return begin;

    while(begin + 1 < end) {

    int midIndex = begin + ((end - begin)>>1);

    if(arr[begin] == arr[midIndex] || arr[end] == arr[midIndex]) {//特殊数组情况

    int min = arr[0];

    int mindex = 0;

    for(int i = 0; i < arr.length; i++) {

    if(arr[i] < min) {

    min = arr[i];

    mindex = i;

    }

    }

    return mindex;

    }

    if(arr[begin] < arr[midIndex] ) {//左侧有序

    begin = midIndex;

    }else {

    end = midIndex;

    }

    }

    return end;

    }

    static int binarySearch(int[] arr, int begin, int end, int target) {

    int midIndex = begin + ((end - begin)>>1);

    while(begin < end) {

    if(target > arr[midIndex]) {

    begin = midIndex + 1;

    }else if(target < arr[midIndex]) {

    end = midIndex - 1;

    }else {

    return midIndex;

    }

    }

    return -1;

    }

    }

    相关文章

      网友评论

          本文标题:旋转数组的任意元素(二分法)

          本文链接:https://www.haomeiwen.com/subject/ntjzjqtx.html