首页 > 试题广场 >

下面关于二分查找的叙述中正确的是：

[单选题]

下面关于二分查找的叙述中正确的是：

表必须有序,表可以顺序方式存储,也可以链表方式存储

表必须有序且表中数据必须是整型,实型或字符型

表必须有序,而且只能从小到大排列

表必须有序,且表只能以顺序方式存储

查看正确选项

smilepoint

跳跃列表是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉查找树 (对于大多数操作需要 O ( log )平均时间)，并且对并发算法友好。

发表于 2015-09-19 13:58:06 回复(0)

蓝夕

答案应该是 D吧，二分查找只能是顺序存储的，有另外一道题选的就是顺序存储和按值排序。

发表于 2016-04-05 22:46:31 回复(0)

huixieqingchun

要注意，二分查找只要满足相应的逻辑结构：有序数组,即可实现。数组的存储结构可以是顺序存储，也可以是链式存储。

发表于 2016-05-02 18:45:04 回复(0)

魅之影_正

正确答案：D

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

它的算法要求是必须是顺序存储结构，必须有序排列

所示选D

编辑于 2015-09-03 11:43:46 回复(4)

MIKE ZHOU

对于链表，我刚开始也有点疑惑。

但我觉得下面这个解释还行得通，你们可以参考下。

先将链表排序；
然后定义一个数组，将链表中每个元素的地址依次放入数组；
这样就可以通过数组->链表元素地址来查找数据了。
由于数组可以用二分查找，所以链表也可用二分查找了。

发表于 2015-11-24 15:40:32 回复(3)

SunburstRun

答案是 A

折半查找也可以用跳表实现，跳表即不是顺序存储

编辑于 2016-06-02 21:13:03 回复(1)

幻之飞雪

我来解释一下跳表

一个普通有序列表的结构如下：

跳表是个概率性数据结构，可以被看作是二叉树的一个变种。跳表是由William Pugh在1990年发明的。它是一种用户维护有序元素的数据结构。

跳表的构造过程是：
1、给定一个有序的链表。
2、选择连表中最大和最小的元素，然后从其他元素中按照一定算法随即选出一些元素，将这些元素组成有序链表。这个新的链表称为一层，原链表称为其下一层。
3、为刚选出的每个元素添加一个指针域，这个指针指向下一层中值同自己相等的元素。Top指针指向该层首元素
4、重复2、3步，直到不再能选择出除最大最小元素以外的元素。

一个跳表，应该具有以下特征：

一个跳表应该有几个层（level）组成；
跳表的第一层包含所有的元素；
每一层都是一个有序的链表；
如果元素x出现在第i层，则所有比i小的层都包含x；
第i层的元素通过一个down指针指向下一层拥有相同值的元素；
在每一层中，-1和1两个元素都出现(分别表示INT_MIN和INT_MAX)；
Top指针指向最高层的第一个元素。

让我们用一个跳表来重新构建开头的有序链表：

通过图我们可以看出，整个跳表分为三层，每一层都是一个有序链表，第一层包含所有的元素。top指针指向最高层的-1元素，较高层的元素都能在较低的层里找到，并且较高层的元素含有一个指针指向下一层值相同的元素。

在结构清晰之后，我们需要明白的是 跳表为什么要这样设计？这么存储的好处是什么呢？ 让我们通过对跳表操作来寻找答案。

首先是查找操作。在跳表中查找一个元素x的算法如下：

p=top;
While(1){
    while (p->next->key < x ) p=p->next;
    If (p->down == NULL ) return p->next;

    p=p->down ;
}

接着是插入算法。假设要插入一个元素“119”，我们设定需要插入该元素的层数为“k”（即我们需要在所有的[1,k]范围内的层里都插入元素。k的值我们会在下文中叙述），则插入算法是：

int insert(val x){
    int i;
    int j = n; //n是当前表所拥有的level数
    cell *p[k]; //指针数组，用来保存每一层要插入元素的前驱
    cell *p1;
    p1 = top->next;
    while(p1){
        while(p1->next->val < x) p1=p1->next;
        if(j <= k){
            p[j-1] = p1; //保存每一层的指针
            p1 = p1->down; //指向下一层
            j--;
        }
    }
    //下面的代码是将x插入到各层
    for (i = 0; i<k; i++){
        if(p[i]==NULL){//k>n的情况，需要创建一个层
            //创建层的第一个元素，并将top指向它
            cell *elementhead = (cell *) malloc(sizeof(cell));
            element->val = -1;
            element->down = top;
            top = elementhead; 
            //创建最后一个元素
            cell *elementtail = (cell *) malloc(sizeof(cell));
            elementtail->val = 1;
            elementtail->next = elementtail->down = NULL;
            //在该层中创建并插入x
            cell *element = (cell *) malloc(sizeof(cell));
            element->val = x;
            elementhead->next = element;
            element->next = elementtail;
            element->down = p[i-1]->next;
        }
        //正常插入一个元素
        cell *element = (cell *) malloc(sizeof(cell));
        element->val = x;
        element->next = p[i]->next;
        element->down = (i=0?NULL:(p[i-1]->next));
        p[i]->next = element;
    }
    return 0;
}

最后是删除操作。 删除一个元素x，如果x被删除后某层只剩下头尾两个节点，则删除这一层。具体算法如下：

int delete(val x){
 
    int i = n; //n表示当前总层数
    cell *p, *p1;
    p = top;
 
    while(n>0){
        while(p->next->val < x) p=p->next;
        if(p->next->val == x){//假如当前层存在节点x,删除
            if(p = top && p->next->next->val == INT_MAX){//该层之存在一个节点
                top = p->down;
                free(p->next->next);
                free(p->next);
                free(p);
                p = top;
            }
            else{
                p1 = p->next;
                p->next = p1->next;
                free(p1);
            }
        }
        p = p->down;
        n--;
    }
}

好了，我们可以看到，无论查找、插入、删除，跳表的时间复杂度都是O(lgn)！这就是为什么我们要引入跳表。

本文参考资料： http://www.kernelchina.org/algorithm/SL.ppt

编辑于 2016-04-30 10:57:32 回复(0)