(五)数据结构之静态查找的简单实现：顺序查找和二分查找

矫情吗；* 2022-06-08 06:14 187阅读 0赞

## 1、查找的定义 ##

根据某个给定关键字K，从集合R中找出关键字与K相同的记录。查找分为动态查找和静态查找：动态查找，集合中内容是动态变化的；静态查找，集合中内容是固定不变的。本文主要来介绍最基本的静态查找的方法：顺序查找和二分查找。

## 2、具体的实现 ##

### 2.1 基本数据结构 ###

/* 定义查找相关数据结构 */
    #define TABLE_LENGTH	10
    typedef int ElementType;
    typedef struct _StaticTable
    {
    	ElementType Element[TABLE_LENGTH + 1];
    	int Length;
    }StaticTable;

### 2.2 顺序查找 ###

/**	顺序查找 
      *		输入参数: Tbl 要查找的顺序表，K 要查找的元素
      *		返回值: 要查找元素的下标，0失败
      */
    int SequentialSearch (StaticTable *Tbl, ElementType K)
    {
    	int i = 0;
    	Tbl->Element[0] = K;
    	for (i = Tbl->Length; Tbl->Element[i] != K; i--);
    	return i;
    }

### 2.3 二分查找 ###

/**	二分查找(数据元素按照由小到大排列)
      *		输入参数: Tbl 要查找的表，K 要查找的元素
      *		返回值: 查找到的元素的下标；0失败，没有找到
      */
    int BinarySearch ( StaticTable * Tbl, ElementType K)
    {
    	int left, right, mid;
    	left = 1;
    	right = Tbl->Length;
    
    	while (left <= right)
    	{
    		mid = (left + right)/2;
    		if (Tbl->Element[mid] > K) right = mid - 1;
    		else if (Tbl->Element[mid] < K) left = mid + 1;
    		else return mid;
    	}
    	return 0;
    }

### 2.4 完整示例代码 ###

#include <stdio.h>
    
    /* 定义查找相关数据结构 */
    #define TABLE_LENGTH	10
    typedef int ElementType;
    typedef struct _StaticTable
    {
    	ElementType Element[TABLE_LENGTH + 1];
    	int Length;
    }StaticTable;
    
    /**	顺序查找 
      *		输入参数: Tbl 要查找的顺序表，K 要查找的元素
      *		返回值: 要查找元素的下标，0失败
      */
    int SequentialSearch (StaticTable *Tbl, ElementType K)
    {
    	int i = 0;
    	Tbl->Element[0] = K;
    	for (i = Tbl->Length; Tbl->Element[i] != K; i--);
    	return i;
    }
    
    /**	二分查找(数据元素按照由小到大排列)
      *		输入参数: Tbl 要查找的表，K 要查找的元素
      *		返回值: 查找到的元素的下标；0失败，没有找到
      */
    int BinarySearch ( StaticTable * Tbl, ElementType K)
    {
    	int left, right, mid;
    	left = 1;
    	right = Tbl->Length;
    
    	while (left <= right)
    	{
    		mid = (left + right)/2;
    		if (Tbl->Element[mid] > K) right = mid - 1;
    		else if (Tbl->Element[mid] < K) left = mid + 1;
    		else return mid;
    	}
    	return 0;
    }
    
    /* 程序入口 */
    int main()
    {
    	int i = 0;
    	int ret;
    	ElementType element;
    	StaticTable tbl;
    
    	/* 给表格赋值 */
    	tbl.Length = TABLE_LENGTH;
    	printf("Input 10 numbers : ");
    	for (i = 1; i <= tbl.Length; i++)
    	{
    		scanf("%d", &tbl.Element[i]);
    	}
    
    	printf("***************************SequentialSearch******************************\n");
    
    	/* 输入要查找的元素 */
    	printf("Input the value that need searching : ");
    	scanf("%d", &element);
    	
    	/* 查找相应元素 */
    	ret = SequentialSearch(&tbl, element);
    
    	if (ret == 0)
    	{
    		printf("Searching is failed!\n");
    	}
    	else 
    	{
    		printf("The searching index is %d, value is %d\n", ret, tbl.Element[ret]);
    	}
    
    	printf("***************************BinarySearch******************************\n");
    
    	/* 输入要查找的元素 */
    	printf("Input the value that need searching : ");
    	scanf("%d", &element);
    
    	/* 通过二分法查找指定元素 */
    	ret = BinarySearch(&tbl, element);
    
    	if (ret == 0)
    	{
    		printf("Searching is failed!\n");
    	}
    	else 
    	{
    		printf("The searching index is %d, value is %d\n", ret, tbl.Element[ret]);
    	}
    	
    	return 0;	
    }