查找的基本概念
 1）查找：在数据集合中寻找满足某种条件的数据元素的过程成为查找。查找的结果一般分为两种：查找成功，即在数据集合中找到了满足条件的数据元素；另一种是查找失败。
 2）查找表(查找结构)：用于查找的数据集合称为查找表，它由同一种类型的数据元素(或者记录)组成，可以使一个数组或链表等数据类型。对查找表经常进行的操作一般有四种：①查询某个特定的数据元素是否在查找表中；②检索满足条件的某个特定的数据元素的各种属性；③在查找表中插入一个数据元素；④从查找表中删除某个数据元素。
 3）静态查找表：如果一个查找表的操作是设计①和②的操作，则无需动态地修改查找表，此类查找表称为静态查找表。与此对应，需要动态地插入或者删除的查找表则称为动态查找表。适合静态查找表的方法有：顺序比较，折半查找，散列查找等。二叉平衡数和B树都是二叉排序树的改进。
 4）关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。比如由一个学生元素构成的数据集合，则学生元素中“学号”这一数据项的值唯一表示一个学生。
 5）平均查找长度：在查找的过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是指所有查找过程中进行关键字的比较次数的平均值。平均查找长度是衡量查找算法效率的最主要的指标。
 
 
顺序查找
 
 
 
概念：顺序查找又称为线性查找，主要用于在线性表中进行查汇总啊。顺序查找通常分为对一般的无序线性表的顺序查找和对按关键字的有序的顺序查找。
 
 
一般的线性表的顺序查找
 
 
 
思想：作为一种最直观的查找方法，其基本思想是从线性表的一端开始，逐个检查关键字是否满足给定的条件。若查找到某个元素的关键字满足给定条件，则查找成功，返回该元素在线性表中的位置；若已经查到表的另一端，还没有查找到符合给定条件的元素，则返回查找失败的信息。
 
 
有序表的顺序查找
 
 
 
概念：如果在查找之前就已经知道了表示按关键字有序的，那么查找失败时可以不用再比较到表的另一端就能返回查找失败的信息，这样能降低顺序查找失败的平均查找长度。
 思想：假设表L是按关键字从小到大排列的，查找的顺序是从前往后查找，待查找元素关键字为key，当查找到第i个元素时，发现第i个元素对应的关键字小于key，但第i+1个圆度对应的关键字大于key，这时就可以返回查找失败的信息了，因为第i个元素之后的元素的关键字均大于key，所以表中不存在关键字为key的元素。
 
 
java代码实现顺序查找：
 
import java.util.Scanner;
/**
 * @author：cch
 * @description：顺序查找
 * @date 2020/12/23
 */

public class MySequentialSearch {
	 	
	
	public static void main(String[] args) {
		int a[]={6,11,23,9,15,78,66,17};
		Scanner sc1=new Scanner(System.in);
		int keytype1=sc1.nextInt();
		System.out.println("关键字在第"+seqsearch(st1,keytype1)+"个位置");		
	}
		public static int seqsearch(int[]a,int keytype){
		if(a.length>0){
			for(int i=0;i<a.length;i++){
				if(a[i]==keytype)   //若查找成功，则返回元素下标i
					return i;
			}
		}
		return -1;   //若查找不成功，返回-1；
	}
}
 
折半查找
 
 
 
概念：折半查找又称为二分查找，它仅适用于有序的顺序表。
 思想：首先将给定值的key与表中中间位置元素的关键字比较，若相等，则查找成功，返回该元素的存储位置；若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分中(例如，在查找升序排列时，若给定值key大于中间元素的关键字，则所查找的元素只可能在后半部分)。然后在缩小范围你继续进行同样的查找，如此重复直到找到为止，或者确定表中没有所需要的查找的元素，则查找不成功，返回失败的信息。
 
 
java代码实现：
 
import java.util.Arrays;

/**
 * @author：cch
 * @description：折半查找
 * @date 2020/12/23
 */
public class HalfSearch {

    public static int biSearch(int[] a, int elem) {
        int n = a.length;
        // 定义低位下标、高位下标、中间位下标
        int low = 0;
        int high = n - 1;
        int mid = 0 ;
        // 二分查找
        while (low <= high) {
            mid = (low + high) / 2;
            System.out.println(a[mid]);
            if (a[mid] == elem) {
                /**
                 * 如果两者相等，则查找成功； 否则利用中间位置的记录
                 * 将数据结构分成前、后两个子数据结构，
                 * 如果中间位置记录的数据大于要查找的数据，则进一步查找前一子数据结构，
                 *  否则进一步查找后一子数据结构。
                 */
                return mid + 1; // 返回数组的下标+1
            } else if (a[mid] < elem) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] test = { 23, 15,9, 11, 520, 998, 216, 789, 601, 35 };
        Arrays.sort(test);
        System.out.println(Arrays.toString(test));
        int elem = 111;
        int res = biSearch(test, elem);
        if (res != -1) {
            System.out.println("查找成功！该元素为第：" + res + "个元素");
        } else {
            System.out.println("查找失败！该元素在数据组中不存在！");
        }
    }
 
分块查找
 
 
 
概念：分快查找又称为索引顺序查找，吸取了顺序查找和折半查找各自的有点，既有动态结构，又适于快速查找。
 思想：将查找表分为若干个子块。块内的元素可以无序，但块之间是有序的，即第一个块中的最大关键字小于第二个块中的所有记录的关键字，第二个块中的最大关键字小于第三个块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各个块的第一个元素的地址，索引表按关键字有序排列。块内是无序的，块间是有序的，例如块2中最大元素小于块3中最小元素。
 分块查找的过程分为两步：第一步在索引表中确定待查找记录所在的块，可以顺序查找或折半查找索引表；第二步在块内顺序查找。
 先用二分查找索引表，确定需要查找的关键字在哪一块，然后再在相应的块内用顺序查找。分块查找又称为索引顺序查找。
 
 
下图所示为一个索引顺序表。
 其中包括三个块，第一个块的起始地址为 0，块内最大关键字为25；
 第二个块的起始地址为 6，块内最大关键字为 55；
 第三个块的起始地址为9，块内最大关键字为 70。
 第三个块的起始地址为13，块内最大关键字为 98。
 分块查找的基本过程如下：
 （1）首先，将待查关键字 K 与索引表中的关键字进行比较，以确定待查记录所在的
 块。具体的可用顺序查找法或折半查找法进行。
 （2）进一步用顺序查找法，在相应块内查找关键字为 K的元素。
 
 java代码实现：
 
import java.util.Arrays;

/**
 * @author：cch
 * @description：折半查找
 * @date 2020/12/23
 */
public class HalfSearch {
	//index代表索引数组，st2代表待查找数组，keytype代表要查找的元素，m代表每块大小
	public static int blocksearch(int[] index,int[]st2,int keytype,int m){
		int i=shunxusearch(index,keytype);    //shunxunsearch函数返回值为带查找元素在第几块
		System.out.println("在第"+i+"块");
		if(i>=0){
		int j=m*i;   //j为第i块的第一个元素下标
		int curlen=(i+1)*m;    
		for(;j<curlen;j++){
			if(st2[j]==keytype)
				return j;
		}
		}
		return -1;
		}
		
		public static void main(String args[]){
		int index[]={25,55,78};
		int st2[]={25, 10, 23, 6, 7, 20, 33, 41, 42, 38, 51, 55, 59, 61, 78, 80, 76, 83};
		System.out.println(blocksearch(index,st2,55,6));
	   }
	}

 
本文实例为大家分享了C语言实现顺序表的顺序查找和折半查找的具体代码，供大家参考，具体内容如下
 
顺序查找：
 
#include 
 
using namespace std;
 
int SeqSearch(int r[],int n,int k)
 
{
 
r[0]=k;//下标0用作哨兵存放要查询的数
 
int i=n;
 
while(r[i]!=k)//不用判断下标i是否越界
 
{
 
i--;
 
}
 
return i;
 
}
 
int main()
 
{
 
int n;
 
cout<
 
cin>>n;
 
int a[n+1];
 
cout<
 
for(int i=1;i<=n;i++)
 
{
 
cin>>a[i];
 
}
 
int k;
 
cout<
 
cin>>k;
 
for(int i=1;i<=n;i++)
 
{
 
cout<
 
}
 
 
cout<
 
cout<
 
 
cout<
 
return 0;
 
 
}
 
 
折半查找：
 
 
#include
 
 
using namespace std;
 
 
int BinSearch1(int r[],int n,int k)//非递归
 
 
{
 
 
int low=1,high=n;//设置查找区间
 
 
while(low<=high)//如果区间存在
 
 
{
 
 
int mid=(low+high)/2;
 
 
if(k
 
else if(k>r[mid])low=mid+1;
 
 
else return mid;
 
 
}
 
 
return 0;//如果区间不存在，则返回0，查找失败
 
 
}
 
 
int BinSearch2(int r[],int low,int high,int k)//递归
 
 
{
 
 
int mid=(low+high)/2;
 
 
if(low>high) return 0;
 
 
else
 
 
{
 
 
if(k
 
else if(k>r[mid])BinSearch2(r,mid+1,high,k);
 
 
else return mid;
 
 
}
 
 
}
 
 
int main()
 
 
{
 
 
int n;
 
 
cout<
 
 
cout<
 
cin>>n;
 
 
int a[n+1];
 
 
cout<
 
 
cout<
 
for(int i=1;i<=n;i++)
 
 
{
 
 
cin>>a[i];
 
 
}
 
 
cout<
 
 
cout<
 
int k;
 
 
cin>>k;
 
 
cout<
 
 
cout<
 
cout<
 
}
 
 
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持脚本之家。
 

C语言顺序表顺序查找和折半查找的基本思想和应用
 
顺序查找算法：又称为线性查找，主要用在—线性表—中进行查找
 通常分为：1—无序线性表的一般查找；
 2—对关键字有序的顺序表查找；
 优缺点分析：
 缺点：当线性表的表长过于长时，平均查找长度较大，效率低。
 优点：对顺序表中数据元素的存储没有要求，顺序存储链式存储均可。
 需注意：对于线性表的链式存储只能使用顺序查找.
 折半查找，又称二分查找，它仅适用于有序的顺序表
 首先将给定值key与表中间位置元素的关键字比较，若相等，则查找成功，返回该元素的存储位置；(例如，在查找表升序排列时，若给定值key大于中间元素的关键字，则所查找的关键字只可能在后半部分)若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分中；然后在缩小范围内继续进行同样的查找，如此重复直到找到为止，若查找不成功，返回查找失败信息
 优缺点分析：
 折半查找方法的优点：折半查找的优点是比较次数少，查找速度快，平均性能好；
 折半查找方法的缺点：折半查找的缺点是：要求待查表为有序表，且插入删除困难。
 因此：折半查找方法适用于不经常变动而查找频繁的有序列表。
 
目的是：⑴ 输入一批整型数据，建立顺序表，然后用顺序查找；
 ⑵ 输入一批有序整型数据（如从小到大），然后用折半查找，查找一给定的整数。
 
#include <stdlib.h>
#define maxsize 20//全局定义

#define OK 1
#define OVERFLOW -2
typedef struct
{
	int key;//关键字
}ElemType;
typedef struct
{
	ElemType *elem;
	int length;
}sqlist;
int initList(sqlist &L)
{
	L.elem=new ElemType[maxsize];//分配数组存储空间
	if(!L.elem) exit (OVERFLOW);
	L.length=0;
	return OK;
}
void display(sqlist &L)//自定义输出函数，将顺序表的key值输出。
{
	int i;
	for(i=0;i<L.length;i++)
		printf("%d ",L.elem[i].key);
	printf("\n");
}
void get(sqlist &L,int size)//3.自定义取值函数利用循环依次为elem[i].key取值，
{
	for(int i=0;i<size;i++)
	{
		scanf("%d",&L.elem[i].key);
	    L.length++;
	}
}
int search(sqlist L,int key)//自定义顺序查找函数，在顺序表L中顺序查找其关键字等于key的数据元素，若找到，则函数值为该元素在表中的位置，否则为0.
{
	for(int i=L.length;i>=1;--i)
		if(L.elem[i].key==key)  return i;
		return 0;
}
int search_Bin(sqlist L,int key)//6.自定义折半查找函数，置查找区间初值，low为1，high为表长；当low小于等于high时，mid取low和high的中间值，将给定值key与中间位置记录的关键字进行比较，若查找成功返回mid，若不相等则利用中间位置记录将表对分成前后两个子表。如果key比中间位置记录的关键字小，则high取为mid-1,否则low取为mid+1；循环结束，说明查找区间为空，则查找失败，返回0.
{
	int low=1,high=L.length,mid;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(key==L.elem[mid].key) return mid;
		else if(key<L.elem[mid].key)  high=mid-1;
		else  low=mid+1;
	}
	return 0;
}


int main()
{
	int m,x,y;
	int m1,x1,y1;
	sqlist L,M;
	initList(L);
	initList(M);
	printf("请输入顺序表的长度(顺序查找)\n");
	scanf("%d",&m);
	printf("请输入一批数据\n");
	get(L,m);
	printf("以下为输入的顺序表(顺序查找)\n");
	display(L);
	printf("请输入你想查找的元素(顺序查找)\n");
	scanf("%d",&x);
	y=search(L,x);
	printf("经过顺序查找发现查找的元素在第%d位\n",y+1);
	printf("请输入顺序表的长度(折半查找)\n");
	scanf("%d",&m1);
	printf("请按由大到小输入一批数据(折半查找)\n");
	get(M,m1);
	printf("以下为输入的顺序表(折半查找)\n");
	display(M);
	printf("请输入你想查找的元素(折半查找)\n");
	scanf("%d",&x1);
	y1=search_Bin(M,x1);
	printf("经过折半查找发现查找的元素在第%d位\n",y1+1);
	return 0;
	


}`
 
 
 
 
C语言数据结构第二版（严蔚敏、李冬梅）著
 

 
线性表的顺序查找和折半查找
 
顺序查找
设置监视哨的顺序查找
非递归折半查找
递归折半查找
代码整合测试

 
顺序查找
 
//顺序查找
int Search_Seq01(SSTable ST,KeyType key)
{
	for(int i=ST.length;i>=1;i--)
		if(ST.R[i].key==key) return i;
	return 0;
}
 
设置监视哨的顺序查找
 
//设置监视哨的顺序查找
int Search_Seq02(SSTable ST,KeyType key)
{
	int i;
	ST.R[0].key = key;
	for(i=ST.length;ST.R[i].key!=key;i--);
	return i;
}
 
非递归折半查找
 
//非递归折半查找
int Search_Bin01(SSTable ST,KeyType key)
{
	int low=1,high=ST.length,mid;    //low和high分别为表的上下界 
	while(low<=high)
	{
		mid=(low+high)/2;     //取中间位置 
		if(ST.R[mid].key==key) return mid;    //找到给定值 
		else if(ST.R[mid].key>key) high = mid-1;   //前往前一个子表 
		else low = mid + 1;    //前往后一个子表 
	}
	return 0;
}
 
递归折半查找
 
//递归折半查找
int Search_Bin02(SSTable ST,KeyType key,int low,int high) 
{
	int mid = (low+high)/2;
	if(ST.R[mid].key==key) return mid;   //找到给定值 
	else if(ST.R[mid].key>key) Search_Bin02(ST,key,low,mid-1);   //前一个子表递归查找 
	else Search_Bin02(ST,key,mid+1,high);        //后一个子表递归查找 
}
 
代码整合测试
 
#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20

typedef int Status;
typedef int KeyType;
typedef int InfoType;
typedef struct
{
	KeyType key;   //关键字域 
	InfoType otherInfo;   //其他域 
}ElemType;
typedef struct
{
	ElemType *R;   //储存空间基地址 
	int length;    //当前长度 
}SSTable;

//初始化一个自定义类型线性表
Status InitTable(SSTable *ST)
{
	ST->R = (ElemType *)malloc(MAXSIZE*sizeof(ElemType));    //开辟空间，别漏了sizeof(ElemType) 
	if(ST->R == NULL) return ERROR;
	ST->length =0;
	return OK;
}

//顺序查找
int Search_Seq01(SSTable ST,KeyType key)
{
	for(int i=ST.length;i>=1;i--)
		if(ST.R[i].key==key) return i;
	return 0;
}

//设置监视哨的顺序查找
int Search_Seq02(SSTable ST,KeyType key)
{
	int i;
	ST.R[0].key = key;
	for(i=ST.length;ST.R[i].key!=key;i--);
	return i;
}

//非递归折半查找
int Search_Bin01(SSTable ST,KeyType key)
{
	int low=1,high=ST.length,mid;    //low和high分别为表的上下界 
	while(low<=high)
	{
		mid=(low+high)/2;     //取中间位置 
		if(ST.R[mid].key==key) return mid;    //找到给定值 
		else if(ST.R[mid].key>key) high = mid-1;   //前往前一个子表 
		else low = mid + 1;    //前往后一个子表 
	}
	return 0;
}

//递归折半查找
int Search_Bin02(SSTable ST,KeyType key,int low,int high) 
{
	int mid = (low+high)/2;
	if(ST.R[mid].key==key) return mid;   //找到给定值 
	else if(ST.R[mid].key>key) Search_Bin02(ST,key,low,mid-1);   //前一个子表递归查找 
	else Search_Bin02(ST,key,mid+1,high);        //后一个子表递归查找 
}

int main()
{
	SSTable ST;
	InitTable(&ST);    //初始化顺序表 
	for(int i=1;i<=20;i++)   //循环赋值 
	{
		ST.R[i].key = i;
		ST.length+=1;
	}
	printf("%d\n",ST.R[Search_Seq02(ST,2)].key);    //由上往下对应查找 
	printf("%d\n",Search_Seq01(ST,3));
	printf("%d\n",Search_Bin01(ST,9));
	printf("%d",Search_Bin02(ST,14,1,20));
	return 0;
}