描述
请编写一个递归的折半查找算法，查找给定有序数组中的某一元素。
输入
多组数据，每组数据有三行。第一行为数组长度n，第二行为n个递增排列的数字，第三行为需要查找的数字k。当n=0时输入结束。
输出
每组数据输出一行，如果可以找到数字，则输出“YES”，否则输出“NO”。
输入样例 1
5
1 4 6 7 8
6
6
1 2 5 7 9 100
8
0输出样例 1
YES NO
思路：
这个题就是折半查找的最基本应用了，折半查找会了这个题就没难度了，能想到的优化方法就是用vector或者是int *的方式开辟一个和n大小一样的数组，避免空间的浪费。
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<stack>
#include<set>
#include<map>
using namespace std;void Create(vector<int>&v,int n)
{int temp;for (int i = 0; i < n; i++){cin >> temp;v.push_back(temp);}
}
void Find(vector<int> v,int x,int low,int high)
{if (low >= high){cout << "NO" << endl;return;}int mid = (low + high) / 2;if (v[mid] == x){cout << "YES" << endl;return;}if (v[mid] < x){low = mid + 1;Find(v, x, low, high);}else{high = mid - 1;Find(v, x, low, high);}}
int main()
{int n;while (cin >> n && n != 0){vector<int> v;Create(v, n);int x;cin >> x;int low = 0, high = n - 1;Find(v, x,low,high);}return 0;
}