查找算法总结

心不留意外尘 2016-04-21

展开全文

http://blog.csdn.net/sunflower_Yolanda/article/details/48497527

这里写图片描述
一、顺序查找：

时间复杂度：O(n)

二、二分查找：

时间复杂度：O(ln(n))。
由于二分查找法每次都取中位数比较，故每轮比较之后，数据都会被丢弃一半（因为待搜索元素绝对不会在这一半里面）所以，设需要搜索次数为x，数据量为n，则在最坏的情况下有2x?1≤n≤2x，即x约等于 ln(n)。
递归方法：

int BinarySearchRecursion(int arry[],int &value,int &start,int &end)
{
    if(start>end)
        return -1;

    int mid=start+(end-start)/2;
    if(arry[mid]==value)
        return mid;

    else if(value<arry[mid])
    {
        end=mid-1;
        return BinarySearchRecursion(arry,value,start,end);
    }
    else
    {
        start=mid+1;
        return BinarySearchRecursion(arry,value,start,end);
    }
}

int BinarySearchRecursion(int arry[],int &len,int &value)
{
    //如果传入的数组为空或者数组长度<=0那么就返回-1。防御性编程
    if(arry==NULL||len<=0)
        return -1;
    int start=0;
    int end=len-1;
    return BinarySearchRecursion(arry,value,start,end);
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

非递归方法：
- 没有重复元素

int binarySearch(vector<int> &A, int target) {
        if (A.size() == 0) {
            return -1;
        }

        int start = 0;
        int end = A.size() - 1;
        int mid;

        while (start + 1 < end) {
            mid = start + (end - start) / 2;
            if (A[mid] == target) {
                end = mid;
            } else if (A[mid] < target) {
                start = mid;
            } else if (A[mid] > target) {
                end = mid;
            }
        }

        if (A[start] == target) {
            return start;
        }
        if (A[end] == target) {
            return end;
        }

        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

有重复元素
- 查找最左边的位置
- 查找最右边的位置
- 统计某个数字出现的次数

//给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。*/

class Solution {
public:
    /**
     * @param array source array
     * @param target target to search
     * @return the first occurrence position of target 
     */
    int binarySearch(vector<int> &A, int target) {
        if (A.size() == 0) {
            return -1;
        }

        int start = 0;
        int end = A.size() - 1;
        int mid;

        while (start + 1 < end) {
            mid = start + (end - start) / 2;
            if (A[mid] == target) {
                end = mid;
            } else if (A[mid] < target) {
                start = mid;
            } else if (A[mid] > target) {
                end = mid;
            }
        }

        if (A[start] == target) {
            return start;
        }
        if (A[end] == target) {
            return end;
        }

        return -1;
    }
};1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

三、分块查找：

时间复杂度：速度介于顺序查找和折半查找之间
步骤：
- 先取各块中的最大关键字构成一个索引表。
- 查找分为两部分，先对索引表进行二分查找或是顺序查找，以确定待查记录在哪一块中。
- 然后，在已经确定的块中用顺序法进行查找。

#import <Foundation/Foundation.h>

struct indexBlock   //定义块的结构
{
    int key;
    int start;
    int end;
} indexBlock[4];   //定义结构体数组


int main(int argc, const char * argv[])
{

    @autoreleasepool {

        int j = -1, k, x;
        int a[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};

        for (int i = 0; i < 3; i++) {
            indexBlock[i].start = j + 1;   //确定每个块范围的起始值
            j = j + 1;       
            indexBlock[i].end = j + 4;     //确定每个块范围的结束值
            j = j + 4;
            indexBlock[i].key = a[j];      //确定每个块范围中元素的最大值
        }

        printf("请输入你要查找的数：\n");
        scanf("%d", &x);
        k = blockSearch(x, a);

        if (k >= 0) {
            printf("查找成功！你要查找的数在数组中的位置是：%d\n", k+1);
        }
        else{

            printf("查找失败！你要查找的数不在数组中。\n");
        }
    }
    return 0;
}

int blockSearch(int x, int a[]){

    int i = 0;
    int j;

    while (i<3 && x>indexBlock[i].key) {  //确定在哪个块中
        i++;
    }

    if (i >= 3) {       //大于分的块数，则返回-1,找不到该数
        return -1;
    }

    j = indexBlock[i].start;    //j等于块范围的起始值

    while (j<=indexBlock[i].end && a[j]!=x) {    //在确定的块内进行查找
        j++;
    }

    if (j > indexBlock[i].end) {       //如果大于块范围的结束值，则说明没有要查找的数，j置为-1
        j = -1;
    }
    return j;1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

四、二叉排序树查找：

二叉搜索树
- 定义：
  - 所有非叶子结点至多拥有两个儿子（Left和Right）
  - 所有结点存储一个关键字
  - 非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；
- 性能：二叉查找树树执行查找的时间与树的深度成正比，即log(n)数量级，在最坏的情况下，二叉查找树可能退化成线性链表，此时二叉查找树的查找时间为O(n)，与顺序表一样
- 查找：
- 查找最小值：最左边的节点
- 查找最大值：最右边的节点
- 求前驱节点：
  - 节点有左子树：前驱一定位于左子树中，且是左子树的最大节点
  - 节点没有左子树：指针不停的向上移动（即node *y = x->parent）,直到x是y的右子树为止
- 求后继节点：
  - 节点有右子树：后继一定位于右子树中，且是左子树的最小节点
  - 节点没有右子树：指针不停的向上移动（即node *y = x->parent）,直到x是y的左子树为止
- 插入：
  - 过程：确定插入位置，插入新的节点
  - 确定插入位置：与根进行比较，如果比根小，那么位于左子树中，否则位于右子树中。查找的过程中记录节点的父节点。一旦发现节点为空，那么父节点就是待插入节点的父节点（当然如果父节点为空，则树为空，此时只需要简单的令根节点等于插入的新节点即可）。然后判断是左子树还是右子树即可。
- 删除
  - 删除的节点为叶子节点：只需将该节点释放，然后将其父节点的指针域做一些“善后”工作即可。
  - 删除的节点有右子树没有左子树：首先要考虑要删除的节点是否可能是根节点，如果是根节点，也好办，因为这是一个只有“右半边”的查找树，直接把根给删了，根节点的右子树作为根节点。如果要删除的节点不是根节点，也好办，如图中的28，直接将右子树交给自己的父亲“照看”。
  - 删除的节点有左子树没有右子树：删除节点后，令右子树变成父节点的右子树即可。
  - 删除的节点有左子树有右子树：
    - 找到要删除节点pnode的中序序列的直接前驱s。（53的就是45，24的就是12）
    - 将pnode的左子树交给pnode的父亲“照顾”
    - 将pnode的右子树交给pnode的直接前驱S”照顾”
  - B-树
    - 定义：
      - 定义任意非叶子结点最多只有M个儿子，且M>2
      - 根结点的儿子数为[2, M]
      - 除根结点以外的非叶子结点的儿子数为[M/2, M]
      - 每个结点存放至少M/2-1（取上整）和至多M-1个关键字（至少2个关键字）
      - 非叶子结点的关键字个数=指向儿子的指针个数-1
      - 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]
      - 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树
      - 所有叶子结点位于同一层
    - 查找：从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点
    - 插入：M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点
    - 删除：需将两个不足M/2的兄弟结点合并
    - 特性：
      - 关键字集合分布在整颗树中
      - 任何一个关键字出现且只出现在一个结点中
      - 搜索有可能在非叶子结点结束
      - 其搜索性能等价于在关键字全集内做一次二分查找
      - 自动层次控制
      - B-树的性能等价于二分查找
  - B+树
    - 定义：其定义基本与B-树同，除了
      - 非叶子结点的子树指针与关键字个数相同
      - 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）
      - 为所有叶子结点增加一个链指针
      - 所有关键字都在叶子结点出现
      - B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找
    - 特性：
      - 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的
      - 不可能在非叶子结点命中
      - 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层
    - 分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针
  - B*树
    - 定义：
      - 是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针
      - B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）
    - 分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。
    - 特性：B*树分配新结点的概率比B+树要低，空间使用率更高
平衡二叉搜索树
- AVL树
  参考数据结构之AVL树
  参考 AVL树(二)之 C++的实现
- 红黑树
  参考教你透彻了解红黑树
- AA树