题目
一个循环有序数组(如: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
的值传递到最外层;
评论区