二分法：二分查找（递归+非递归）实现

二分查找又称折半查找，首先，假设表中元素是按升序排列，将 表中间位置的关键字与查找关键字比较:

1. 如果两者相等，则查找成功;
2. 否则利用中间位置将表分成前、后两个子表:
   1)如果中间位置的关键字大于查找关键字，则进一步查找前一子表
   2)否则进一步查找后一子表 重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

例如：target = 200
arr = [-1,2,5,20,90,100,320]

使用二分查找，从arr中查找target是否存在

1. 取中间位置为20 ，20 < 200
2. 缩小查找空间 [90,100,320]，二分查找中间位置100 < 200
3. 缩小查找空间[320,320],begin == end
4. 未找到 200，返回失败

问题描述如下：
已知一个排序数组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(n*m)即O(n^2);
这里使用二分查找则仅仅需要O(log2n)的时间复杂度:
n/2 + n/4 + … + n/2^k (k为循环的次数)
由于你n/2^k （取最坏的情况，最后一次仅剩下一个数）
即令n/2^k=1
可得k=log2n,（是以2为底，n的对数）
所以时间复杂度可以表示O(h)=O(log2n)

递归实现如下:

bool find_part(std::vector<int> arr, int begin, int end, int target) {
	if (begin > end) {//结束条件
		return false;
	}
	int mid = (begin + end) / 2;
	if (arr[mid] == target) {
		return true;
	} else if (arr[mid] > target) {
		return find_part(arr, begin, mid -1, target);
	} else {
		return find_part(arr, mid + 1, end, target);
	}
}

std::vector<int> get_result(std::vector<int> arr, std::vector<int> target) {
	std::vector<int> v;
	for (int i = 0;i < target.size(); ++i) {
		int result = find_part(arr,0,arr.size() - 1, target[i]);
		v.push_back(result);
	}

	return v;
}

非递归实现：

std::vector<int> find_part_norecur(std::vector<int> arr1, std::vector<int> target) {
	std::vector<int> result;
	for (int i = 0;i < target.size(); ++i) {
		int begin = 0;
		int end = arr1.size();
		while(begin < end) {
			int mid = (begin +  end) / 2;
			if(arr1[mid] == target[i]) {
			    result.push_back(1);
			    break;
			} else if (arr1[mid] > target[i]) {
				end = mid - 1;
			} else {
				begin = mid + 1;
			}
		}
		if (begin >= end){
			result.push_back(0);
		}
	}
	return result;
}

测试代码如下:

#include <iostream>
#include <vector>

using namespace std;

bool find_part(std::vector<int> arr, int begin, int end, int target) {
	if (begin > end) {
		return false;
	}

	int mid = (begin + end) / 2;
	if (arr[mid] == target) {
		return true;
	} else if (arr[mid] > target) {
		return find_part(arr, begin, mid -1, target);
	} else {
		return find_part(arr, mid + 1, end, target);
	}
}

std::vector<int> get_result(std::vector<int> arr, std::vector<int> target) {
	std::vector<int> v;
	for (int i = 0;i < target.size(); ++i) {
		int result = find_part(arr,0,arr.size() - 1, target[i]);
		v.push_back(result);
	}

	return v;
}

std::vector<int> find_part_norecur(std::vector<int> arr1, std::vector<int> target) {
	std::vector<int> result;
	for (int i = 0;i < target.size(); ++i) {
		int begin = 0;
		int end = arr1.size();
		while(begin < end) {
			int mid = (begin +  end) / 2;
			if(arr1[mid] == target[i]) {
			    result.push_back(1);
			    break;
			} else if (arr1[mid] > target[i]) {
				end = mid - 1;
			} else {
				begin = mid + 1;
			}
		}
		if (begin >= end){
			result.push_back(0);
		}
	}
	return result;
}

int main(int argc, char const *argv[])
{
	std::vector<int> arr1;
	std::vector<int> target;
	int n;
	cin >> n;
	for (int i = 0;i < n; ++i) {
		int tmp;
		cin >> tmp;
		arr1.push_back(tmp);
	}

	int t;
	cin >> t;
	for (int i = 0;i < t; ++i) {
		int tmp;
		cin >> tmp;
		target.push_back(tmp);
	}	

	std::vector<int> result;
	// result = get_result(arr1, target);
	result = find_part_norecur(arr1,target);
	for (int i = 0;i < result.size(); ++i) {
		cout << result[i] << " ";
	}
	return 0;
}

输出如下:

#输入序列数组
5   
2 3 4 5 6
#输入目标数组
3
1 3 5
#输出
0 1 1