侧边栏壁纸
博主头像
惊羽博主等级

hi ,我是惊羽,前生物学逃兵,现系统工程沉迷者 . 贝壳签约工程师 , 曾被雇佣为 联拓数科 · 支付研发工程师 、京东 · 京东数科 · 研发工程师、中国移动 · 雄安产业研究院 · 业务中台技术负责人 .

  • 累计撰写 100 篇文章
  • 累计创建 14 个标签
  • 累计收到 9 条评论

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

惊羽
2021-06-30 / 0 评论 / 0 点赞 / 334 阅读 / 1,194 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2021-09-03,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

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

0
广告 广告

评论区