【算法】折半查找解析

​​

活动地址：CSDN21天学习挑战赛

作者：柒号华仔
个人主页：欢迎访问我的主页
个人信条：星光不问赶路人,岁月不负有心人。
个人方向：主要方向为5G，同时兼顾其他网络协议，编解码协议，C/C++，linux，云原生等，感兴趣的小伙伴可以关注我，一起交流。

1. 折半查找介绍

1.1 定义

折半查找也称二分查找，是一种在有序数组中查找某一特定元素的搜索算法，每一次查找，搜索范围均缩小一半，效率较高。如果数组是乱序状态，则应排序，再进行查找。

1.2 基本原理

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半 。

1.3 时间复杂度与空间复杂度

总共有n个元素，每次查找的区间大小就是n，n/2，n/4，…，n/$2^k$，一直到1，其中k就是循环的次数。
由于n/$2^k$取整后>=1，即令n/$2^k$=1，可得k=log2n,（是以2为底，n的对数），所以时间复杂度可以表示O()=O(logn)。

二分查找只需要额外存储三个变量：最大值 ，最小值 和 中点，空间复杂度为常数 O(1)。

1.4 优缺点

优点：比较次数少，查找速度快，平均性能好。
缺点：要求待查表为有序表，且插入删除困难。

2. 代码实现

2.1 代码设计

1. 输入需要查找的元素，我们输入的是38；left是有序数组最左端0，是最小值，right是有序数组最右端10，是最大值，mid为数组1/2位置，即array[5]；
2. 38比array[5] = 19大，因此left等于原mid+1，即array[6] = 26，right不变；新mid为(left+right)/2 = （6+10）/2 = 8；
3. 38比array[8] = 36大，因此left等于上一次mid+1，即array[9] = 38，right不变；新mid为(left+right)/2 = （9+10）/2 = 9；
4. 38等于array[9]，mid与left重合， 查找成功，返回数组下标9.
   
   

2.2 代码实现

#include 
#include 

int binarySearch(int array[],int len,int target){
    int left = 0;
    int right = len - 1;
    while(left <= right){
        int mid = (right + left) / 2;
        if(array[mid] == target){
            return mid;
        } else if(array[mid] < target){
            left = mid + 1;
        } else if(array[mid] > target){
            right = mid - 1;
        }
    }
    return -1;
}

int main(void)
{
    int array[]={2,3,4,5,15,19,26,27,36,38,45};
    int key = 0,ret;

    printf("请输入需要查找的数字:");
    scanf("%d",&key);

    ret = binarySearch(array,sizeof(array)/sizeof(int),key);
    if(ret < 0)
        printf("查找失败\n");
    else
        printf("该数字为数组第%d个元素\n",ret+1);

    return 0;
}

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

运行结果：

请输入需要查找的数字:38
该数字为数组第10个元素