折半查找——（递归，非递归C语言实现）

折半查找

1. 基本概念：
   1）折半查找（对半查找、二分查找）：
   (a)在==有序表（假设为递增）<先排序>==中，取中间记录作为比较对象。
   (b)
   若给定值与中间记录相等，则查找成功；
   若给定值小于中间记录，则在有序表的左半区继续查找;
   若给定值大于中间记录，则在有序表的右半区继续查找。
   不断重复上述过程，直到查找成功，或查找区域无记录，查找失败
   
2. 例子：
   
   PS：
   mid=(low+high)/2
   若出现：low>high 则查找失败
3. 代码：（非递归）

int BinSearch(int r[],int n,int k)
{
	int mid,low=1,high=n;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(k<r[mid])
		{
			high=mid-1;
		}
		else 
		{
			if(k>r[mid])
			{
				low=mid+1;
			}
			else
			{
				return mid;
			}
	}
	return 0;//查找失败返回0
}

1. 代码：（递归）

int BinSearch(int r[],int low,int high,int k)
{
	int mid;
	if(low>high) return 0;
	else
	{
		mid=(low+high)/2;
		if(k<r[mid])
		{
			return BinSearch(r,low,mid-1,k);
		}
		else
		{
			if(k>r[mid])
			{
				return BinSearch(r,mid+1,high,k);
			}
			else
			{
				return mid;
			}
		}
	}
}

（只是书写格式不同）

int BinSearch(int r[],int low,int high,int k)
{
	int mid;
	if(low>high) return 0;
	else
	{
		mid=(low+high)/2;
		if(k<r[mid]) return BinSearch(r,low,mid-1,k);
		else if(k>r[mid]) return BinSearch(r,mid+1,high,k);
		else return mid;
	}
}

1. 折半查找判定树：
   1）判定树（折半查找判定树）：描述折半查找判定过程的二叉树
   2）设查找区间是[low, high]，判定树的构造方法：
   （1）当low＞high时，判定树为空；
   （2）当low ≤ high时，
   判定树的根结点是有序表中序号为mid=(low+high)/2的记录，
   根结点的左子树是与有序表r[low]~r[mid-1]相对应的判定树，
   根结点的右子树是与有序表r[mid+1] ~ r[high]相对应的判定树。
   
   3）结论：
   （1）折半查找任一记录的过程，即是判定树中从根结点到该记录结点的路径。
   （2）给定值的比较次数=该记录结点在树中的层数
   4）查找成功情况下，与判定树的深度有关，判定树的深度是多少呢？
   
   5）查找不成功：
   
   查找不成功的过程是从根结点到外部结点的路径，和给定值进行的比较次数等于该路径上内部结点的个数。
   6）再上图中：
   查找成功的平均比较次数 = (1×1+2×2+3×4+4×4)/11 = 3
   <需要比较一次的一个，需要比较2次的2个，需要比较三次的4个，需要比较四次的4个>
2. 例题：

有一个按照元素值排好序的顺序表（长度大于2），分别用顺序查找和折半查找与给定值相等的元素，比较次数分别是s和b，在查找成功的情况下，s和b的关系是（）；在查找不成功的情况下，s和b的关系是（）。

1.不一定
2.s>b

1. 实验：

【问题描述】
从键盘读入一串整数和一个待查关键字，查找在该整数串中是否有这个待查关键字。如果有，输出它在整数串中的位置；如果没有，输出-1。
实验要求：用递归或非递归方式实现折半查找算法
【输入形式】
首先输入一个n表示一串整数的长度，再输入一个m表示待查关键字，接下来输入n个具体元素。
【输出形式】
输出对应位置的编号或-1
【样例输入】
5 6
1 2 3 5 6
【样例输出】
5

#include<stdio.h>

//1)非递归查找
void BinSearch1(int arr[],int high,int m)
{
	int low,mid;
	low=1;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(m==arr[mid]) {printf("%d\n",mid); return ;}
		else if(m<arr[mid]){ high=mid-1; }
		else { low=mid+1; }	
	}
	if(low>high)
	{
		printf("-1\n");
	}
}

//2)递归查找 
void BinSearch2(int arr[],int low,int high,int m)
{
	int mid;
	if(low>high) printf("-1\n");
	else 
	{
		mid=(low+high)/2;
		if(m>arr[mid]) return BinSearch2(arr,mid+1,high,m);
		else if(m<arr[mid]) return BinSearch2(arr,low,mid-1,m);
		else printf("%d\n",mid);
	}

}

int main()
{
	int n,m,i,j,temp;
	scanf("%d %d",&n,&m);
	int arr[n];
	for(i=1;i<=n;i++)
	{
		scanf("%d",&arr[i]);
	}
	//排序 
	for(i=1;i<=n-1;i++)
	{
		for(j=1;j<=n-1-i;j++)
		{
			if(arr[j+1]<arr[j])
			{
				temp=arr[j+1];
				arr[j+1]=arr[j];
				arr[j]=temp;
			}
		}
	}
	BinSearch1(arr,n,m);
	BinSearch2(arr,1,n,m);
	return 0;
}