c++实现二分查找

最后更新于:2022-04-01 20:19:42

# 简要描述 **二分查找**又称折半查找,对排好序的数组,每次取这个数和数组中间的数进行比较,复杂度是O(logn)如:设数组为a[n],查找的数x, 如果x==a[n/2],则返回n/2; 如果x < a[n/2],则在a[0]到a[n/2-1]中进行查找; 如果x > a[n/2],则在a[n/2+1]到a[n-1]中进行查找; **优点**是比较次数少,查找速度快,平均性能好;其**缺点**是要求待查表为有序表,且插入删除困难。 条件:**查找的数组必须要为有序数组。** # 二种实现方式 ### 1.递归 ~~~ /* 归的二分查找 arrat:数组 , low:上界; high:下界; target:查找的数据; 返回target所在数组的下标 */ int binarySearch(int array[], int low, int high, int target) { int middle = (low + high)/2; if(low > high) { return -1; } if(target == array[middle]) { return middle; } if(target < array[middle]) { return binarySearch(array, low, middle-1, target); } if(target > array[middle]) { return binarySearch(array, middle+1, high, target); } } ~~~ ### 2.非递归(循环) ~~~ /* 非递归的二分查找 arrat:数组 , n:数组的大小; target:查找的数据; 返回target所在数组的下标 */ int binarySearch2(int array[], int n, int target) { int low = 0, high = n, middle = 0; while(low < high) { middle = (low + high)/2; if(target == array[middle]) { return middle; } else if(target < array[middle]) { high = middle; } else if(target > array[middle]) { low = middle + 1; } } return -1; } ~~~ 推荐使用非递归的方式,因为递归每次调用递归时有用堆栈保存函数数据和结果。**能用循环的尽量不用递归。** # 二分查找的应用 还是对上一篇博文《[C++如何跳出多层循环](http://blog.csdn.net/luoweifu/article/details/16369007)》中提到的抽签问题进行分析。 上一篇博文中是进行了四重循环的嵌套,基时间复杂度是O(n4),数据大时其计算量会大的惊人。为便于分析,将之前代码帖至如下:

**
抽签问题
解决方案,复杂度n^4 
*/ 
void  drawLots() {
   //从标准输入读入
   int numOfCard, sum;
   int k[MAX_N];
   cout<<"输入numOfCard和sum"<<endl;
   cin>>numOfCard>>sum; 
   cout<<"请输入这sum张卡片的数字"<<endl;
   for(int i=0; i<numOfCard; i++) {
cin>>k[i];
   }
   bool result = false;
   bool isBreakLoop = true;
   int _sum = 0;
   for(int a = 0; a < numOfCard && isBreakLoop; a ++) {
      for(int b = 0; b < numOfCard && isBreakLoop; b ++) {
          for(int c = 0; c < numOfCard && isBreakLoop; c++) {
              for(int d = 0; d < numOfCard && isBreakLoop; d ++) {
              	_sum = k[a] + k[b] + k[c] + k[d];
                  if(_sum == sum) {
result = true;
isBreakLoop = false;
                  }	 
              }
          }
      }
   }
   cout << "_sum:" << _sum << "  " << "sum:" << sum << endl;
   if(result){
   	cout<<"Yes"<<endl;
   } else
    cout<<"No"<<endl;
}

最内层循环所做事如下: Ka + kb + kc + kd = m 移项后如下: Kd = m - (Ka + kb + kc) 到第四层循环时,其实Ka ,kb,kc已经知道,那问题也就变成了对kd的查找,我们可用上面讲的二分查找,复杂度就降为O(n3logn).实现如下: ### 降低复杂度的实现

/**
抽签问题 
解决方案,复杂度n^3 * log(n)
*/ 
void drawLots2() {
int numOfCard, sum;
int k[MAX_N];
cout<<"输入numOfCard和sum"<<endl;
    cin>>numOfCard>>sum; 
    cout<<"请输入这sum张卡片的数字"<<endl;
    for(int i=0; i<numOfCard; i++) {
cin>>k[i];
    }
    //对数组进行排序 
    sort(k, k + numOfCard);
int index = -1;
    bool isBreakLoop = true;
    for(int a = 0; a < numOfCard && isBreakLoop; a ++) {
    	for(int b = 0; b < numOfCard && isBreakLoop; b ++) {
        	for(int c = 0; c < numOfCard && isBreakLoop; c++) {
        	index = binarySearch2(k, numOfCard, sum - (k[a] + k[b] + k[c]));
            	if(index >= 0) {
isBreakLoop = false;
                }
          	}
      	}
}
   if(index >= 0){
   	cout<<"Yes"<<endl;
   } else
    cout<<"No"<<endl;
}

### 进一步优化[O(n2logn)] 根据上一步的优化方式,我们可以进一步对内侧两层循环(也就是第三层和第四层)进行思考: Kc+ kd = m - (Ka + kb ) 我们不能直接对Kc+ kd进行查找,但是可以预先枚举出Ka + kb 的n2种数值并排序,再对Kc+ kd进行十分查找。列出枚举O(n2),排序O(n2logn), 循环O(n2logn),所以总的复杂度降为O(n2logn),实现如下:

/**
抽签问题 
解决方案,复杂度n^2 * log(n)
*/ 
void drawLots3() {
int numOfCard, sum;
int k[MAX_N];
cout<<"输入numOfCard和sum"<<endl;
    cin>>numOfCard>>sum; 
    cout<<"请输入这sum张卡片的数字"<<endl;
    for(int i=0; i<numOfCard; i++) {
cin>>k[i];
    }
    int cdNum = numOfCard*(numOfCard+1)/2;
    int cdSum[cdNum];
    int i = 0;
    for(int a=0; a<numOfCard; a++) {
    	for(int b=i; b<numOfCard; b++) {
    	cdSum[i ++] = k[a] + k[b];
    	}
    }
    //对数组进行排序 
    sort(cdSum, cdSum + cdNum);
int index = -1;
    bool isBreakLoop = true;
    for(int a = 0; a < numOfCard && isBreakLoop; a ++) {
    	for(int b = 0; b < numOfCard && isBreakLoop; b ++) {
        	for(int c = 0; c < numOfCard && isBreakLoop; c++) {
        	index = binarySearch2(cdSum, cdNum, sum - (k[a] + k[b]));
            	if(index >= 0) {
isBreakLoop = false;
                }
          	}
      	}
}
   if(index >= 0){
   	cout<<"Yes"<<endl;
   } else
    cout<<"No"<<endl;
}

### 进一步思考 上面枚举Ka + kb 时其实是有重复的,因为k[i] + k[j] == k[j] + k[i],去除重复值之后,Ka + kb 值的个数是n(n+1)/2。至于n(n+1)/2怎么来,可以简单推导如下: N     M 1     1 2      2+1 3     3+2+1 4     4+ 3+2+1 ...... 实现如下:

/**
抽签问题 
解决方案,复杂度n^2 * log(n)
*/ 
void drawLots3_1() {
int numOfCard, sum;
int k[MAX_N];
cout<<"输入numOfCard和sum"<<endl;
    cin>>numOfCard>>sum; 
    cout<<"请输入这sum张卡片的数字"<<endl;
    for(int i=0; i<numOfCard; i++) {
cin>>k[i];
    }
    int cdNum = numOfCard*numOfCard;
    int cdSum[cdNum];
    for(int a=0; a<numOfCard; a++) {
    	for(int b=0; b<numOfCard; b++) {
    	cdSum[a*numOfCard + b] = k[a] + k[b];
    	}
    }
    //对数组进行排序 
    sort(cdSum, cdSum + cdNum);
int index = -1;
    bool isBreakLoop = true;
    for(int a = 0; a < numOfCard && isBreakLoop; a ++) {
    	for(int b = 0; b < numOfCard && isBreakLoop; b ++) {
        	for(int c = 0; c < numOfCard && isBreakLoop; c++) {
        	index = binarySearch2(cdSum, cdNum, sum - (k[a] + k[b]));
            	if(index >= 0) {
isBreakLoop = false;
                }
          	}
      	}
}
   if(index >= 0){
   	cout<<"Yes"<<endl;
   } else
    cout<<"No"<<endl;
}
 
';