查找-折半查找（二分查找）

喜欢ヅ旅行 2022-05-13 08:42 351阅读 0赞

**折半查找**

折半查找，也称为二分查找。其要求是数据是有序的，即表中元素按关键字有序。

比如有序表是递增有序的。首先取这表中的中间的数据与关键值（给定值key）比较的关系。若key>表的中间值，则说明key存在于表的中间值的右侧。因此，中间值右侧的区间又要取出中间值再与key比较，以此类推，直至查找成功或者区间缩小为0时还找不到就结束。

若key有与表中某区间 的中间值相等，则说明查找成功。

若表的区间缩小为0时，仍然没有找到与key相匹配的值，就说明key不在表中。

**特点：**只适合用于顺序存储结构，而不适用于链式存储结构。表必须要求是**有序表**。

**时间复杂度：**

O(log2(n))

**折半查找的基本思路：**

![70][]

**优点：**效率高，平均性能好

**缺点：**插入删除困难

**代码：**

(1)

#include<stdio.h>
    #define MAXL 10
    typedef struct
    {
    	int key;
    }NodeType;
    typedef NodeType SeqList[MAXL];
    int BinSearch(SeqList r,int n,int k)
    {
    	int left=0,right=n-1,mid;
    		printf("\n中间值：");
    	while(left<=right)
    	{
    		mid=(left+right)/2;
    			printf("%d  ",mid);
    		if(r[mid].key==k)
    		{
    		
    				return mid;
    		}
    		
    		if(r[mid].key>k)
    			right=mid-1;
    		else
    			left=mid+1;
    	}
    	return -1;
    }
    void main()
    {
    	SeqList r;
    	int k=7;
    	int a[10]={0,1,2,3,4,5,6,7,8,9},i,n=10;
    	for(i=0;i<n;i++)
    		r[i].key=a[i];
    	printf("关键字序列：");
    	for(i=0;i<n;i++)    
    	{
    		printf("%d  ",r[i].key);
    	}
    	if((i=BinSearch(r,n,k))!=-1)
    		printf("\n元素%d的位置是%d\n",k,i);
    	else
    		printf("元素%d不在表中\n",k);
    }

(2)

#include<stdio.h>
    int BinSearch(int arr[],int n,int k)
    {
    	int left=0,right=n-1,mid;
    		printf("\n中间值：");
    	while(left<=right)
    	{
    		mid=(left+right)/2;
    			printf("%d  ",mid);
    		if(arr[mid]==k)
    		{
    		
    				return mid;
    		}
    		
    		if(arr[mid]>k)
    			right=mid-1;
    		else
    			left=mid+1;
    	}
    	return -1;
    }
    void main()
    {
    
    	int k=7;
    	int a[10]={0,1,2,3,4,5,6,7,8,9},i,n=10;
    	printf("关键字序列：");
    	for(i=0;i<n;i++)    
    	{
    		printf("%d  ",a[i]);
    	}
    	if((i=BinSearch(a,n,k))!=-1)
    		printf("\n元素%d的位置是%d\n",k,i);
    	else
    		printf("元素%d不在表中\n",k);
    }

[70]: /images/20220513/d5e1b7abbc764de29b25173a93bf2822.png