二分搜索法-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;
}