旋转数组查找指定值

男娘i 2022-05-12 04:04 127阅读 0赞

递增数组\[1,2,3,4,5\]，变化为\[5,6,1,2,3,4\]， 给定K，判断是否存在，并返回其索引位置  
二分查找  
选择中间位置作为判断的分界点  
所以二分中，必定有一部分数组是递增有序的，而另一部分则不是，所以当我们取中间点的时候，首先判断中间点是不是所要寻找的值。  
如果不是，则寻找递增的那一部分数组  
1.前部分是递增数组，如果指定值在前部分数组中，end = mid - 1；否则在后部分数组中，begin =mid + 1  
2.后部分是递增数组，如果指定值在后部分数组中，begin = mid + 1，否则在前部分数组中，end = mid - 1  
3.如果begin,mid,end处的值是相等的，那么只能顺序遍历

package sordoffer;
    
    /** * 递增数组[1,2,3,4,5]，变化为[5,6,1,2,3,4] * 给定K，判断是否存在，并返回其索引位置 * 思路： * 1.选择中间点middle作为拐点 * 2.a[middle] > a[low] middle左边数组是有序的 * k <= a[middle] && k >= a[low]，可以在左边数组查找。 * 否则在右边数组查找 * a[middle] < a[high] middle的右边数组是有序的 * k >= a[middle] && k <= a[high] , 可以在右边数组查找， * 否则在左边数组查找 */
    public class FindKReverseArray { 
        public int findK(int[] arr,int k){
            int begin = 0;
            int end = arr.length - 1;
            while (begin < end){
                int mid = (begin + end) >> 1;
                if (k == arr[mid])
                    return mid;
                if (arr[mid] == arr[begin] && arr[begin] == arr[end]){
                    return FindInOrder(arr,k);
                }
                //前部分是递增数组
                if (arr[mid] > arr[begin]){
                    if (k >= arr[begin]  && k <= arr[mid]){
                        end = mid - 1;
                    }else{
                        begin = mid + 1;
                    }
                }else{  //后部分是递增数组
                    if (k >= arr[mid] && k <= arr[end])
                        begin = mid + 1;
                    else
                        end = mid - 1;
                }
            }
            return -1;
        }
    
        private int FindInOrder(int[] arr, int k) {
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] == k)
                    return i;
            }
            return -1;
        }
    }