循环有序数组，查找值

佚名 6年前 (2019-06-23) 算法 2047人围观抢沙发百度已收录

一、从一个循环有序数组总查找给定值

　　1、思路：先通过中间值和最后一个或者第一个元素比较，找出局部有序范围，再通过二分查找局部有序段

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

private static int sortArrFindOne(int arr[], int low, int high, int target) {
        int mid = (high - low) / 2 + low;
        if (arr[mid] == target) return mid;
        if (arr[mid] < arr[high]) {
            if (arr[mid] < target && target <= arr[high]) {
                return find(arr, mid, high, target);
            } else {
                return sortArrFindOne(arr, low, mid, target);
            }
        } else {
            if (arr[low] <= target && target < arr[mid]) {
                return find(arr, low, mid, target);
            } else {
                return sortArrFindOne(arr, mid, high, target);
            }
        }
    }

　　2、找局部有序（二分递归查找）

//局部有序
    private static int find(int arr[], int low, int high, int target) {
        int mid = (high - low) / 2  + low;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) {
            return find(arr, mid + 1, high, target);
        } else {
            return find(arr, low, mid - 1, target);
        }
    }

　　3、测试

public static void main(String[] args) {
        int arr[] = {6, 7, 8, 9, 1, 2, 3, 4, 5};
        System.out.println(sortArrFindOne(arr, 0, arr.length - 1, 8));
        System.out.println(sortArrFindOne(arr, 0, arr.length - 1, 1));
        System.out.println(sortArrFindOne(arr, 0, arr.length - 1, 5));
        System.out.println(sortArrFindOne(arr, 0, arr.length - 1, 6));
    }