二分查找/折半查找——C语言实现

ゝ一世哀愁。 2023-06-03 02:58 2阅读 0赞

**折半查找**的应用前提是数组是一个有序数组。比较数组中间值和查找值的大小关系，然后确定下一步的查找范围，逐次缩小。折半查找的时间复杂度为O(log2(n))，是一种效率很高的查找方式。  
**程序实现**

#include <stdio.h>
    #include <math.h>
    
    int search(int key, int a[], int len)
    {
        int left = 0, right = len-1;
        int mid = 0;
        int res = -1;
        while( right > left )
        {
            mid = (left+right)/2;
            if( a[mid] == key)
            {
                res = mid;
                break;
            }
            else if( a[mid]>key )
            {
                right = mid-1;
            }
            else
            {
                left = mid+1;
            }
        }
        
        return res;
    }
    
    
    int main()
    {
        int a[] = {2,4,5,7,9,12,14,16,35,79};
        int len = sizeof(a)/sizeof(a[0]);
        int x;
        printf("请输入要查找的数：");
        scanf("%d",&x);
        int r = search(x,a,len);
        if(r!=-1)
        {
            printf("%d所在的位置为：%d\n",x,r);
        }
        else
        {
            printf("这里没有要查找的数。\n");
        }
        return 0;
    }

**运行结果**  
![在这里插入图片描述][20191005143453812.png]  
![在这里插入图片描述][20191005143758676.png]  
前面说过折半查找的时间复杂度为O(log2(n))，据此我们也可以得到一些常见的说法。

也即是说在100个数中查找，最多7次就可以找到；在1000个数中查找，最多10次就可以找到。

[20191005143453812.png]: /images/20230601/ed4ab0ade19c474d82d617b24211f870.png
[20191005143758676.png]: /images/20230601/8c144faf72e04ce58e97d7ea3dfafc8e.png