面试算法:在未知长度的排序数组中进行快速查找

假设A是一个排好序的数组,但是它的长度,我们无法得知。如果我们访问的元素超出了数组长度,那么就会引发一次异常,请设计一个有效算法,输入数组A以及一个数值k,找到一个下标i,使得A[i] = k, 返回-1,如果数组A中不存在等于k的元素。

这道题跟我们以前处理的查找问题不同之处在于,数组A的长度无法确定。如果数组A长度确定的话,那么问题就退化为一个在排序数组中进行查找的问题,此时我们依靠二分查找法就能快速定位数组A是否包含给定元素。

问题在于,数组A长度无法提前确定,那么我们就不能直接使用二分查找,因为我们无法定位中点,在使用二分查找时,我们需要知道起点b,终点e,然后定位中点m = (b+e)/2, 然后看A[m]与要查找数值的关系,如果A[m]大于k,那么我们就可以在[b,e]中二分查找,如果A[m]小于k,那么我们就可以在[b,e]中二分查找。由此当e不能确定时,我们无法计算m。

在不确定长度的排序数组中进行查找时,我们可以这么做。我们依次查找A[0],A[1],A[2],A[4],…,如果A[i]比k小,那么我们就将当前访问元素的下标增加一倍,假定A[p]比k小,但是访问A[2p]时越界产生了异常,那么我们就在区间[p, 2p]间进行二分查找,当然如果在产生异常前,我们找到p,使得A[p]大于k,那么我们就可以直接在区间[0, p]间进行二分查找就可以了。我们看看相关的实现代码:

public class SearchingUnkownLengthSortedArray { 

    private int[] array = null; 

    public SearchingUnkownLengthSortedArray(int[] A) { 
        this.array = A; 
    } 

    private int binarySearch(int[] A, int k, int begin, int end) { 
        /* 
         * 在区间[begin, end]中进行二分查找,如果找到则返回下标,找不到则返回-1 
         */ 
        while (begin <= end) { 
            int m = (begin + end) / 2; 
            //如果访问A[m]出现异常,那么把end设置为m-1,然后继续执行二分查找 
            try { 
                if (A[m] == k) { 
                    return m; 
                } 

                if (A[m] < k) { 
                    begin = m + 1; 
                } 

                if (A[m] > k) { 
                    end = m - 1; 
                } 

            }catch (ArrayIndexOutOfBoundsException e) { 
                System.out.println("mid point out of length: " + m); 
                end = m - 1; 
            } 
        } 

        return -1; 
    } 

    public int searchingWithUnknownLength(int k) { 
        /* 
         * 下标从0,1,2依次倍增,如果下标增加到2p时,访问越界,那么在[p, 2p]间进行二分查找 
         */ 
        if (this.array[0] == k) { 
            return 0; 
        } 

        if (this.array[0] > k) { 
            return -1; 
        } 

        int endKeeper = 1; 
        while (true) { 
            try { 
                if (this.array[endKeeper] < k) { 
                    endKeeper = endKeeper << 1; 
                } else if (this.array[endKeeper] == k){ 
                    return endKeeper; 
                }else { 
                    return this.binarySearch(this.array, k, 0, endKeeper); 
                } 
            }catch(ArrayIndexOutOfBoundsException e) { 
                System.out.println("index out of array length: " + endKeeper); 
                return this.binarySearch(this.array, k, endKeeper >> 1, endKeeper); 
            } 
        } 

    } 

}

注意到代码实现中,有两处对数组下标访问溢出进行了捕捉。一是倍增下标,探测数组结尾时会产生数组访问溢出,二是在binarySearch中进行二分查找时,由于给定的末尾很可能远远超出数组末尾,因此获取中点m时任然有可能产生数组访问溢出,在二分查找时,一旦出现溢出,我们可以确定数组末尾一定在当前计算的中点之前,因此调整二分查找的区间末尾后,再次进行查找即可,注意代码实现中,从没有考虑数组长度。

我们构造一个排序数组,然后调用上面代码查询给定元素,相关代码如下:

public class Searching { 
     public static void main(String[] args) { 
         int A[] = {1, 2, 3, 4 , 5, 6, 7, 8, 9 , 10}; 
         SearchingUnkownLengthSortedArray su = new SearchingUnkownLengthSortedArray(A); 
         int idx = su.searchingWithUnknownLength(10); 
         if (idx != -1) { 
             System.out.println("The given key is at index of " + idx); 
         } else { 
             System.out.println("The array do not contain the given key"); 
         } 
     } 
}

上面代码运行后如图:

上面代码运行的时间复杂度是lg(n),其中n是数组的长度。

原文发布于微信公众号 - Coding迪斯尼(gh_c9f933e7765d)

原文发表时间:2018-07-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java初学

13.2 具体的集合

2749
来自专栏Java帮帮-微信公众号-技术文章全总结

第十八天 集合-泛型&list接口&set接口【面试+工作】

泛型的使用:一般在创建对象时,将未知的类型确定具体的类型。当没有指定泛型时,默认类型为Object类型。

1112
来自专栏有趣的Python

4-Java常用工具类-集合

问题: 存储20名学生的学生信息。20是不变的,就是这么多。 问题: 存储商品信息。不知道自己要买多少商品。

1962
来自专栏尾尾部落

[算法总结] 一文搞懂面试链表题

链表是面试过程中经常被问到的,这里把剑指offer 和 LeetCode 中的相关题目做一个汇总,方便复习。

1161
来自专栏java学习

ArrayList集合常用的方法详细讲解

在前面我们学习了数组,数组可以保存多个元素,但在某些情况下无法确定到底要保存多少个元素,此时数组将不再适用,因为数组的长度不可变。例如,要保存一个...

1844
来自专栏编程心路

在ArrayList的循环中删除元素,会不会出现问题?

在 ArrayList 的循环中删除元素,会不会出现问题?我开始觉得应该会有什么问题吧,但是不知道问题会在哪里。在经历了一番测试和查阅之后,发现这个“小”问题并...

4492
来自专栏Python爱好者

Java基础笔记14

1173
来自专栏java一日一条

Java程序员们最常犯的10个错误

Arrays.asList()会返回一个ArrayList对象,ArrayList类是Arrays的一个私有静态类,而不是java.util.ArrayList...

571
来自专栏CDA数据分析师

算法和数据结构—— 查找和排序

本文为简书作者郑永欣原创,CDA数据分析师已获得授权 查找和排序都是程序设计中经常用到的算法。查找相对而言较为简单,不外乎顺序查找、二分查找、哈希表查找和二叉排...

2306
来自专栏LanceToBigData

JavaSE(八)之集合概述

前几天其实一直在学习关于linux的内容和kvm虚拟化的知识。今天有时间来回顾一下集合相关的知识,接下来我将带大家一起来回顾一起集合关联的知识。 不要辜负自己花...

1845

扫码关注云+社区

领取腾讯云代金券