C语言经典查找算法之二分查找（详解）

墨蓝 2023-01-03 14:19 92阅读 0赞

### 文章目录 ###

*   *  一、查找算法
     *  二、二分查找算法

## 一、查找算法 ##

查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。

## 二、二分查找算法 ##

**1、算法思想**  
该查找算法又称为 折半查找，二分查找，适合对已经排序好的数据集合进行查找，时间复杂度O（log2n）,效率高。  
假设有一升序的数据集合，先找出升序集合中最中间的元素，将数据集合划分为两个子集，将最中间的元素和关键字key进行比较，，如果等于key则返回，如果大于关键字key，则在前一个数据集合中查找，否则在后一个子集中查找，直到找到为止，如果没找到则返回-1。

**2、二分查找步骤**  
（1）首先确定整个查找区间的中间位置mid=(low+high)/2;

（2）用待查关键字值与中间位置关键字值进行比较；若相等，则查找成功；

（3）若大于，则在后半个区域中继续进行折半查找。  
若小于，则在前半个区域中继续进行折半查找。

（4）查找成功，返回关键字所在数组下标，没找到返回-1；

**3、二分查找C语言实现**

#include <stdio.h>
    #define MaxSize 100
    typedef struct
    { 
    	int list[MaxSize];
    	int length;
    }Table;
    int BinarySearch(Table S, int x);
    
    void main()
    { 
    	Table T={ { 11,22,33,44,55,66,77,88,99},9};
    	int i, find, x;
    	printf("有序表中的元素：\n");
    	for(i=0; i<T.length; i++)
    		printf("%4d", T.list[i]);
    	printf("\n请输入要查找的元素：");
    	scanf("%d",&x);
    	find= BinarySearch(T, x);
    	if(find)
    		printf("元素%d是顺序表中的第%d个元素。\n", x, find);
    	else
    		printf("没有找到该元素！\n");
    }
    
    //在有序表中折半查找元素x，如果找到，则返回该元素在表中的位置，否则返回0 
    int BinarySearch(Table S, int x)
    { 
    	int low, high, mid;
    	low=0, high=S.length-1;  //设置待查找元素范围的下界和上届 
    	while(low<=high)
    	{ 
    		mid= (low+high)/2;
    		if(S.list[mid]==x)  //如果找到元素，则返回该元素所在的位置 
    			return mid+1;
    		else if(S.list[mid]<x)  //如果mid所指示的元素小于x，则修改low指针
    			low= mid+1;
    		else if(S.list[mid]>x)  //如果mid所指示的元素大于x，则修改high指针 
    			high= mid+1; 
    	}
    }

![01][]

参考文献：《The Function and Algorithm of Program Language C/C++》

[01]: /images/20221119/f66c80d330bf47d48193011bf159864d.png