二分查找
已知一个排序数组A，如A= [-1,2,5,20,90,100,207,800] 另外一个乱序数组B,如B =[50,90,3,-1,207,80] 求B中的任意某个元素，是否在A中出现，结果存储在数组C中，出现用1代表，未出现用0代表，如，C = [0,1,0,1,1,0]。
最暴力的方法： o(n2) 折半查找： 对于某个元素是（logn）,如果有那个元素就是（nlogn）。
std::vector<int> search_array(std::vector<int> & sort_array, std::vector<int> &random_array){
}二分查找又称折半查找，假设表中元素是按升序排列，将表中间位置的关键字与查找关键字比较: 1.如果两者相等，则查找成功; 2.否则利用中间位置将表分成前、后两个子表: 1)如果中间位置的关键字大于查找关键字，则进一步查找前一子表 2)否则进一步查找后一子表 重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
递归版本：
#include<vector>
bool binary_search(std::vector<int> &sort_array, int begin, int end, int target){
if(begin > end ){
return false;// 区间不存在！
}
int mid = (begin + end) / 2 ;//找中点
if(target == sort_array[mid]){
return true；
}
else if( target == sort_array[mid]){//在左区间查找
return binary_search(sort_array, begin, mid-1,target);
}
else if(){
return binary_search(sort_array, mid +1, end, target);
}
}循环实现：
bool binary_search(std::vector<int> &sort_array, int target){
int begin = 0;
int end = sort_array.size() -1;
while(begin <= end){
int mid =(begin + end)/ 2;
if(target == sort_array[mid]){
return true;
}
else if(target < sort_array[mid]){
end = mid -1;
}
else if(target > sort_array[mid]){
begin = mid +1;
}
}
return false;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.03.23 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读