折半搜索，也称二分搜索、对数搜索，是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半 。

注意：元素序列一定是要有序的，乱序的情况下不可以使用折半查找。

数组a头尾分别为start和end，那么它们的中点元素下标mid(start+end)/2。如果a[mid]=target(目标元素)，那么直接得出元素存在于数组的结论；如果a[mid]<target，说明target位于[mid+1,end]这个区间；如果a[mid]>target，说明target位于[start,mid-1]这个区间；如果start>end，说明查找结束，target不存在。
这就是为什么序列一定要求有序的原因了。如果序列无序，那么通过a[mid]和target的大小来判断target所在区间这个就会出错。

数组a为｛2 4 5 6 8 9 10 12 16 20｝，使用折半查找的方式查找元素10的过程：
当前搜索的子序列：
2 4 5 6 8 9 10 12 16 20
a[mid]=8
当前搜索的子序列：
9 10 12 16 20
a[mid]=12
当前搜索的子序列：
9 10
a[mid]=9
当前搜索的子序列：
10
a[mid]=10
元素存在

数组a为｛1 3 4 6 7 8 10 11 13｝，使用折半查找的方式查找元素9的过程：
当前搜索的子序列：
1 3 4 6 7 8 10 11 13
a[mid]=7
当前搜索的子序列：
8 10 11 13
a[mid]=10
当前搜索的子序列：
8
a[mid]=8
元素不存在

数组a为｛2 4 6 7 8 9 11 13 14 15 18｝，使用折半查找的方式查找元素8的过程：
当前搜索的子序列：
2 4 6 7 8 9 11 13 14 15 18
a[mid]=9
当前搜索的子序列：
2 4 6 7 8
a[mid]=6
当前搜索的子序列：
7 8
a[mid]=7
当前搜索的子序列：
8
a[mid]=8
元素存在

数组a为｛2 4 6 7 8 9 11 13 14 15 18｝，使用折半查找的方式查找元素12的过程：
当前搜索的子序列：
2 4 6 7 8 9 11 13 14 15 18
a[mid]=9
当前搜索的子序列：
11 13 14 15 18
a[mid]=14
当前搜索的子序列：
11 13
a[mid]=11
当前搜索的子序列：
13
a[mid]=13
元素不存在

因为每一轮都只搜索数组一半的元素，所以待搜索的元素数量以指数下降。时间复杂度即O(logN)，其中log以2为底数。

#include<iostream>
#include<stdio.h> 
using namespace std;
int length;
int flag = 0;

void showList(int a[],int start,int end){
	cout<<"当前搜索的子序列："<<endl;
	for(int i=start;i<=end;i++){
		cout<<a[i]<<" ";
	} cout<<"\n";
	
} 

void binary_search(int a[],int start,int end,int target){
	if(start>end){//搜索失败
		return ;
	}
	int mid = (start+end)/2;
	if(a[mid]==target){//查找成功
		flag = 1;
		return ;
	}else if(a[mid]>target){//中间元素大于目标元素，说明目标元素位置可能在中间元素之前
		binary_search(a,start,mid-1,target);//新的搜索序列为中间位置之前
	}else{//中间元素小于目标元素，说明目标元素位置可能在中间元素之后
		binary_search(a,mid+1,end,target);//新的搜索序列为中间位置之后
	}
	
}

int main(){
	int a[20];
	cout<<"请输入元素个数:";
	cin>>length;
	for(int i=0;i<length;i++){
		cin>>a[i];
	} 
	int target; 
	cout<<"请输入目标元素:";
	cin>>target;
	binary_search(a,0,length-1,target);
	if(flag==1){
		cout<<"元素存在"<<endl;
	}else{
		cout<<"元素不存在"<<endl;
	}
	return 0;
}

敬请批评指正