折半查找概念
 
折半查找，又称二分查找。
 前提是线性表中的记录必须是关键码有序(由小到大或由大到小)，线性表必须采用顺序存储。
 折半查找的基本思想是：在有序表中，取中间值为比较对象，如果给定的值和中间值的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定的值大于中间值的关键字，则在中间记录的右半区继续查找。重复上述过程，直到查找成功，或查找所有区域无记录，返回查找失败。
 
算法实现
 
	public int Binary_Search(int[] a, int n, int key) {
		int low = 1, high = n, mid;
		while(low <= high) {
			mid = (int)((low + high) / 2);
			if(key < a[mid]) {
				high = mid - 1;
			}
			else if(key > a[mid]) {
				low = mid + 1;
			}
			else return mid;
		}
		
		return 0;
	}
 
通常会使用三个指针low，high，mid。分别表示查找区域的最左值下标，查找区域的最右值下标，已经当前比对值下标。
 
时间复杂度分析
 
折半查找其实等于是把静态有序查找表分成了两棵子树，即查找经过只需要找其中的一半数据即可，等于工作量少了一半，以提升效率。
 完全二叉树存在定义：
 
 
 
具有n个节点的我拿权二叉树深度为log2n + 1
 
 
尽管折半查找判定二叉树并不是完全二叉树，但同样相同的推倒可以得到关键字或查找失败的次数是log2n + 1。最好为情况下查询次数为1。所有折半查找算法的时间复杂度为O(logn + 1)。
 
缺点
 
折半查找的前提是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，这个时候不建议使用。

 
一、解题思路
 
1.宏定义数组元素个数为ARRNUM=10
 函数原型声明void AscendSorting(int a[]);
 函数原型声明int Bisearch(int x,int *a[],int left, int right);
 
2.设计函数
 2.1设计函数void AscendSorting(int a[])
 2.1.1函数功能
 函数功能为实现对数组进行由小到大排序，排序方法选择效率较高的选择法
 2.1.2 函数内部
 定义变量int i=0,j=0，k=0;
 使用循环的嵌套实现由小到大的排序
 2.1.3 循环内部
 外层循环for(i=0;i<ARRNUM;i++)内对k进行赋值k=i
 内层循环for(j=i+1;j<ARRNUM;j++)内用if语句判断a[j]<a[k]是否成立，成立则k=j
 内层循环结束则用if语句判断k!=i是否成立，成立则令a[i]=a[k]
 
2.2设计函数 int Bisearch(int x,int *a[],int left,int right)
 2.2.1函数功能
 如果找到对应数，函数返回值为对应数组下表，否则返回-1
 函数功能为运行折半查找法，在一个有序序列中查找某一特定的数
 2.2.2函数内部
 定义变量mid并初始化为0，int mid=0;
 用while循环实现查找，当查找范围下界小于等于查找范围上界时执行循环，循环判断条件是left<=right
 循环内部
 每一次循环开始时，将mid初始化为查找范围的中位数对应下标，mid=left+(right-left)/2
 用else-if语句判断x与a[mid]大小关系
 如果x==a[mid],则函数返回值为1
 如果x<=a[mid],则令查找范围上界更改为right=mid-1，继续循环
 如果x>=a[mid],则令查找范围下界更改为left=mid+1，继续循环
 如果循环结束，仍为找到用户输入值x，则令函数返回则为-1
 
3.主函数内部
 3.1 变量定义
 定义用户输入的数为x、rt，分别初始化为0、-1
 定义数组并初始化a[ARRNUM]={78,99,27,33,54,11,37,28,88,38}
 3.2 数组排序
 调用AscendSorting函数实现数组升序排列
 3.3 用for循环实现有序数组打印输出
 3.4 读入数据
 printf函数提示用户要查找的数，scanf函数读入用户要查找的数x
 3.5 输出查找结果
 将Bisearch函数返回值赋值给rt,rt=Bisearch(x,a,0,sizeof(a)/sizeof(0)-1)
 用else-if语句判断rt==-1 是否成立，成立则输出未找到，否则输出找到
 
二、实验代码
 #define ARRNUM 10
 void AscendSorting(int *a)
 {
 int i=0,j=0,k=0,inter=0;
 for(i=0;i<ARRNUM-1;i++)
 {
 k=i;
 for(j=i+1;j<ARRNUM;j++)
 {
 if(a[j]<a[k]) k=j;
 }
 if(i != k)
 {
 inter=a[i];
 a[i]=a[k];
 a[k]=inter;
 }
 }
 
#include<stdio.h>
 #include"Bisearch.h"
 int main(void)
 {
 int x=0,rt=0,i=0;
 int Left=0,Right;
 int a[ARRNUM]={78,99,27,33,54,11,37,28,88,38};
 Right=9;
 AscendSorting(a);
 printf(“The array after sorting:\n”);
 for(i=0;i<ARRNUM;i++)
 {
 printf("%d",a[i]);
 printf(" “);
 }
 printf(“Please input the number you want to search within 100:\n”);
 scanf(”%d",&x);
 rt=Bisearch(x,a,Left,Right);
 if(rt==-1)
 {
 printf(“未找到”);
 }
 else
 {
 printf(“找到了%d,在数组第%d个”,x,rt+1);
 }
 return 0;
 }

适用范围：
 
二分查找算法又叫折半查找算法，算法的效率是很高的，这点毋庸置疑，但其有自己特有的使用范围，仅可以查找有序的数列，对于无序、乱序的数列是不适用的
 
方法思维：
 
每次将查找的数列进行折半拆分，也就是一分为二的思想理念，每次匹配一个部分，重复多次，即可查询到相应的数字。
 
 
 
例如：
 一个[a,b]的闭区间，想查找一个该区间内的值
 将区间一分为2
 第一个为[a , (a+b)/2] 第二个区间为[(a+b)/2，b]
 将需要查找的数分别与这两个区间的最大值和最小值比较
 如果在该区间，则将该区间再次进行拆分，重复多次，直到求解。
 
 
例题：
 
 
 
编写代码在一个整形有序数组中查找具体的某个数
 要求：找到了就打印数字所在的下标，找不到则输出：找不到。
 
 
#include <stdio.h>
//二分查找
/*编写代码在一个整形有序数组中查找具体的某个数
要求：找到了就打印数字所在的下标，找不到则输出：找不到*/
int main()
{
	//定义这个整型有序数组
	int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13 };
	//获取数组中元素的个数
	int num = sizeof(arr) / sizeof(int);
	int left = 0;
	int right = num - 1;
	printf("请输入您要查找的数：");
	int search;
	scanf("%d", &search);
	for (int i = 0; i < num; i++)
	{
			int mid = (left + right) / 2;


			if (arr[mid] > search)
			{
				right = mid + 1;


			}
			else if (arr[mid]<search)
			{
				left = mid + 1;
			}
			else
			{
				printf("找到这个数了，这个数的下标为\"%d\"\n", mid);
				printf("这个数为\"%d\"\n", arr[mid]);
				break;
			}
	
		if (left > right)
		{
			printf("找不到这数！");


		}
	}
		
	return 0;
}

题目
 
编写一个函数，利用二分查找算法在一个有序表中插入一个关键字k，并保持表的有序性。
 
分析
 
先在有序表中利用二分查找算法查找关键字值等于或小于k的结点，m指向正好等于k的结点或l指向关键字正好大于k的结点，然后采用移动法插入k结点即可。
 
本题的难点就是如何利用二分查找算法找到合适的插入位置。
 
有两种情况：第一种是有序表中没有等于关键字k的结点，寻找大于k的结点即可；第二种是有序表中存在等于关键字k的结点，寻找等于k的结点即可。
 
图解如下：
 
 
将两种情况用同一部分代码来处理，定义一个标志位变量flag，用来记录是否有等于关键字k的情况，初始为0表示没有等于关键字k的情况，如果有则将flag置为1，然后退出循环，最终根据标志位flag来判断插入位置。
 
代码
 
核心代码：
 
/* 使用二分查找在顺序表中插入元素k */ 
void insertK(int nums[],int n,int k){
	int mid;// 记录中间下标 
	int low=0,high=n-1;
	int flag=0;// 标志，用来记录是否有等于k的值 
	int pos;// 定义的变量，为插入的位置 
	while(low<=high&&flag==0){// 循环当low>high时跳出循环 
		mid=(low+high)/2;
		if(nums[mid]==k){
			flag=1;// 如果发现有关键字等于k,则将标志flag置为1，退出循环然后插入k 
		}else if(nums[mid]>k){
			high=mid-1;
		}else if(nums[mid]<k){
			low=mid+1;
		}
	}
	/* 确定插入位置 */ 
	if(flag==1){// 如果flag为1则发现序列中有关键字等于k，则使插入位置等于mid
		pos=mid; 
	}else{// 如果flag为0则表示序列中没有与关键字k相等的值，则插入位置为low 
		pos=low;
	}
	/* 插入关键字k */
	for(int i=n-1;i>=pos;i--){
		nums[i+1]=nums[i];
	} 
	nums[pos]=k;
}
 
完整代码如下：
 
#include<stdio.h>

/* 打印数组 */ 
void printArr(int nums[],int n){
	printf("\n");
	for(int i=0;i<n;i++){
		printf("%d\t",nums[i]);
	}
	printf("\n");
}

/* 使用二分查找在顺序表中插入元素k */ 
void insertK(int nums[],int n,int k){
	int mid;// 记录中间下标 
	int low=0,high=n-1;
	int flag=0;// 标志，用来记录是否有等于k的值 
	int pos;// 定义的变量，为插入的位置 
	while(low<=high&&flag==0){// 循环当low>high时跳出循环 
		mid=(low+high)/2;
		if(nums[mid]==k){
			flag=1;// 如果发现有关键字等于k,则将标志flag置为1，退出循环然后插入k 
		}else if(nums[mid]>k){
			high=mid-1;
		}else if(nums[mid]<k){
			low=mid+1;
		}
	}
	/* 确定插入位置 */ 
	if(flag==1){// 如果flag为1则发现序列中有关键字等于k，则使插入位置等于mid
		pos=mid; 
	}else{// 如果flag为0则表示序列中没有与关键字k相等的值，则插入位置为low 
		pos=low;
	}
	/* 插入关键字k */
	for(int i=n-1;i>=pos;i--){
		nums[i+1]=nums[i];
	} 
	nums[pos]=k;
}

int main(){
	int nums[]={1,2,3,4,5,6,7};
	int n=7;
	int k=5;
	insertK(nums,n,k);// 插入k
	printArr(nums,n);// 打印数组 
	
	return 0;
}
 
运行结果：