二分搜索法-C++
二分法，就是对一个数组中，已经排好序的数字进行搜索。
使用二分法的前提条件：
1.是一个数组
2.该数组中的数字已经是有序的，比如升序的数字或者降序的数字都可以。int a[]={1,2,3,4}; int b[]={4,3,2,1};
3.该数组中没有出现重复的数字
二分法原理：
就是对一个数组，不断的划分出一个一个的区间，不断的缩小区间的范围，直至找到该数字为止。
比如：现在有一个数组 int a[] = {1,2,3,4,5,6,7,8,9,10};
需要查找的数字是 ：9
如果使用常规方法，就是对数组下标进行遍历，如果找到则输出下标，然后结束循环。但是这样子需要循环9次才能得到结果。
for(int i = 0;i<10;i++){
if(a[i]==9){
cout<<i;
break;
}
}
但是会发现有一个问题，当数字很多的时候，1000万个，1亿个数字的时候，甚至更多n个数字的时候，极限情况需要循环1000万、1亿次、n次，是挺消耗时间的。
但是使用二分法需要的时间只需要log2n次即可，大大缩减了循环次数。
下面是使用二分法思路来解决这个问题：
第一步：当前查找的下标范围是 a[0]---a[9],这时候的中间位置的数字是a[0+(9-0)/2]=a[4]=5。
a[4]<9,也就是说明a[0]----a[4]之间的数字肯定也是小于9的，所以下一步就可以直接看a[5]------a[9]这个区间的数字
第二步：当前查找的下标范围是a[5]------a[9]，这时候的中间位置的数字是a[5+(9-5)/2]=a[7]=8。
a[7]<9,也就是说明a[5]----a[7]之间的数字肯定也是小于9的，所以下一步就可以直接看a[8]------a[9]这个区间的数字
第三步：当前查找的下标范围是a[8]------a[9]，这时候的中间位置的数字是a[8+(9-8)/2]=a[8]=9。
a[8]=9,也就是刚好查找到了，并且所在的位置是下标8
二分结束！
例题：给定一个有序数组，对该数组进行查找一个数字是否存在，是的话返回该数字所在的位置，不是的话则返回-1。
//target 查找的目标数字
//left左边区间的下标
//right右边区间的下标
int er_search(int a[],int target,int left,int right){
while(left<=right){
int mid = left+(right-left)/2;//当前从左到右的区间的中间位置
if(a[mid] == target){
return mid;
}
else if(a[mid]<target){
left = mid+1;
//mid+1的原因是a[mid]小于target,
//所以下一步不需要从a[mid]----a[right] 这个范围内去找了
//应该可以直接从 从a[mid+1]----a[right] 这个范围内去找了
}
else{
//这里与上面同理
right= mid-1;
}
}
return -1;
}