已知一个排序数组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;
}