算法练习(19) - 查找循环有序数组任一数值的位置

题目

一个循环有序数组（如：3,4,5,6,8,9,11,0,1,2），要查找任一数值的位置。要求算法时间复杂度为log2(n)。
输入：数组 和 待查找元素
输出：返回数组元素下标，如果不存在返回-1
循环有序数组即原本有序数组折断后产生的，可认为数组原本排序是递增的，且不包含重复元素。

答案

import java.util.*;
public class Main {
    public static void main(String[] args) {
        
        int[] arr = {3,4,5,6,8,9,11,0,1,2};
        int left = 0;
        int right = arr.length -1;
        int target = 11;
        
        int index = getNumberIndex(arr ,left,right,target);
        System.out.print(index);
    }
    
    public static int getNumberIndex(int[] arr ,int left,int right,int target) {
        if(left == right){
            if(arr[left] == target){
                return left;
            }else {
               return -1; 
            }
        }
        int middle =  (left + right) / 2;
        int respre = getNumberIndex(arr,left,middle,target);
        int ressuf =  getNumberIndex(arr,middle + 1,right,target);
        return respre == -1 ? ressuf : respre;
    }
}

思路

递归 + 二分 + 分治;

分 :

分到最后一定是聚焦到单个值,也就是说每个元素都会被访问一遍;

聚合 :

对二分后的数组没有聚合的需求,只需要吧结果聚合一下就行 return respre == -1 ? ressuf : respre; 这一行意思是, 在递归返回的时候,结果一定是从单值传递上来的,所以,我们为了保证正确结果能够传递到最外层递归,使用三目来让 != -1 的值传递到最外层;