ddddfang's Blog.

binary-search

binary-search
字数统计: 829阅读时长: 4 min
2019/02/11 Share

二分查找(注意二分查找的前提是: 这个数组是有序的~):

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


int binary_search(int* a, int len, int goal, int left)    //left代表若查到多个目标,是否需要返回最左边的那个
{
    int low = 0;
    int high = len -1;
    int lastPos = -1;        //default: 没找到
    while (low <= high)
    {
        int middle = (high - low) / 2 + low;        // 直接使用(high + low) / 2 可能导致溢出
        if (a[middle] == goal)                //直接return 则 "若goal有重复==>随机返回其中一个index"
        {
            lastPos = middle;                //这里记录上次已经找到的goal,并让他继续找
            if(left)
                high = middle-1;
            else
                low = middle+1;
        }
        else if (a[middle] > goal)        //在左半边
            high = middle - 1;
        else                                                //在右半边
            low = middle + 1;
    }
    return lastPos;
}

因为二分查找需要数组提前有序,所以下面的demo使用快速排序来处理数组

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
int Partition(int a[], int start, int end) //返回调整后基准数的位置
{
    int i = start, j = end;
    int x = a[i]; //a[i]就是第一个坑，这里可以先安排一个a[i] <---> a[randint(start,end)]
    while (i < j)
    {
        // 坑在左边，那就先从右向左找小于x的数来填a[i]
        while(i < j && a[j] >= x)
            j--;
        if(i < j)
        {
            a[i] = a[j]; //将a[j]填到a[i]中，a[j]就形成了一个新的坑
            i++;
        }
                      // 从左向右找大于或等于x的数来填a[j]
        while(i < j && a[i] < x)
            i++;
        if(i < j)
        {
            a[j] = a[i]; //将a[i]填到a[j]中，a[i]就形成了一个新的坑
            j--;
        }
    }
    //退出时，i等于j。将x填到这个坑中。
    a[i] = x;
    return i;
}

void _qsort(int *a, int start, int end)
{
    if(start >= end)
    {
        return;
    }
    int i = Partition(a,start,end);
    _qsort(a, start, i-1);
    _qsort(a, i+1, end);
}

void Qsort(int *a, int len)
{
    if(a == NULL || len <= 0)
        return;
    int start = 0;
    int end = len -1;
    _qsort(a, 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
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
65
66
67
68
69
70
71
72
73
74
75
76
77
#define NUM 1000
int main()
{
    int i = 0;
    int *abc = malloc(NUM*sizeof(int));
    srand(0); //生成随机种子

    printf("\n====================随机生成 %d 个数==============================\n",NUM);
    for(i=0;i<NUM;i++)
    {
        abc[i] = rand()%(10*NUM);
        printf("%d ",abc[i]);
    }
    printf("\n");
    printf("\n====================快速排序后结果==============================\n");

    Qsort(abc,NUM);
    for(i=0;i<NUM;i++)
    {
        printf("%d ",abc[i]);
    }
    printf("\n");
    printf("\n====================检查快速排序结果正确性========================\n");

    for(i = 0;i<NUM-1;i++)
    {
        if(abc[i]>abc[i+1])
        {
            printf("ERROR!!!,i=%d\n",i);
            break;
        }
        if(abc[i] == abc[i+1])
        {
            printf("found a equal,i=%d,value %d\n",i,abc[i]);
        }
    }
    if(i == NUM-1)
        printf("good,sort is ok\n");
    printf("\n==================二分查找某个数字是否存在===========================\n");
    printf("\n");
    int target = 123;
    int index = binary_search(abc, NUM, target, 0);
    printf("target %d, index is %d\n",target,index);
    if(index != -1)
        printf("abc[%d] = %d",index,abc[index]);

    printf("\n==========对数组中每个数均二分查找一下，检查二分查找正确性==================\n");

    for(i=0;i<NUM;i++)
    {
        target = abc[i];
        index = binary_search(abc, NUM, target, 1);
        if(index == -1)
        {
            printf("ERROR,the value %d exist but you do not find out\n",target);
            break;
        }
        if(abc[index] != target)
        {
            printf("ERROR,you found a error index!,abc[%d] is not equals to %d\n",index,target);
            break;
        }
    }
    if(i == NUM)
        printf("binary_search check ok\n");

    printf("\n==================特殊情况检查================================\n");

    int tmp[] = {3,3,3,3,3,3,3,3,3,3,3};
    target = 3;
    index = binary_search(tmp, sizeof(tmp)/sizeof(int), target, 1);
    printf("%d\n",index);
    index = binary_search(tmp, sizeof(tmp)/sizeof(int), target, 0);
    printf("%d\n",index);
    printf("\n======================over============================\n");
    return 0;
}

原文作者：ddddfang

原文链接：https://ddddfang.github.io/2019/02/11/binary-search/

发表日期：February 11th 2019, 2:54:56 pm

更新日期：February 11th 2019, 3:11:57 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
Total : 42
2019
binary-search bitmap caffe c++ 单例模式 common misc makefile 宏 顺序容器 智能指针 排序 shell linux command docker blog ffmpeg gdb gitbook p4 printf 可变参数 static and dynamic library 第k小的数 ubuntu setup 并查集 git draw.io markdown vscode office2016 密钥 键值对集合 链表 最大堆(大顶堆) swig python c vim 红黑树 skip-list hash-table
algorithm-and-data-struct caffe common-misc cpp linux-daily ffmpeg