Binary search

A binary search algorithm (or binary chop) is a technique for finding a particular value in a sorted list. It makes progressively better guesses, and closes in on the sought value, by comparing an element halfway with what has been determined to be an element too low in the list and one too high in the list. A binary search finds the median element in a list, compares its value to the one you are searching for, and determines if it’s greater than, less than, or equal to the one you want. A guess that turns out to be too high becomes the new top of the list, and one too low the new bottom of the list. The binary search's next guess is halfway between the new list's top and bottom. Pursuing this strategy iteratively, it narrows the search by a factor 2 each time, and finds your value. A binary search is an example of a divide and conquer algorithm (more specifically a decrease and conquer algorithm) and a dichotomic search (more at Search algorithm). The most common application of binary search is to find a specific value in a sorted list. To cast this in the frame of the guessing game (see Example below), realize that we are now guessing the index, or numbered place, of the value in the list. This is useful because, given the index, other data structures will contain associated information. Suppose a data structure containing the classic collection of name, address, telephone number and so forth has been accumulated, and an array is prepared containing the names, numbered from one to N. A query might be: what is the telephone number for a given name X. To answer this the array would be searched and the index (if any) corresponding to that name determined, whereupon it would be used to report the associated telephone number and so forth. Appropriate provision must be made for the name not being in the list (typically by returning an index value of zero), indeed the question of interest might be only whether X is in the list or not. If the list of names is in sorted order, a binary search will find a given name with far fewer probes than the simple procedure of probing each name in the list, one after the other in a linear search, and the procedure is much simpler than organising a hash table though that would be faster still, typically averaging just over one probe. This applies for a uniform distribution of search items but if it is known that some few items are much more likely to be sought for than the majority then a linear search with the list ordered so that the most popular items are first may do better. The binary search begins by comparing the sought value X to the value in the middle of the list; because the values are sorted, it is clear whether the sought value would belong before or after that middle value, and the search then continues through the correct half in the same way. Only the sign of the difference is inspected: there is no attempt at an interpolation search based on the size of the differences. Your task is to write a program that, given a set numbers of ascending and a key, finding a particular postion in a sorted list.

输入

The input contains one total numbers（N<=5000000） and a find key,followed by a line containing the integer numbers ascending sets. 

输出

if find the key in the sorted list, output containing postion in a sorted list, else ouput -1.

样例输入

10 7
0 1 2 3 4 5 6 7 8 9

样例输出

8

Google翻译启动：由于题目太长，就截取了部分重要的片段

二元搜索首先将搜索到的值X与列表中间的值进行比较; 因为值是排序的，所以很明显所寻求的值是否属于该中间值之前或之后，然后搜索以相同的方式继续通过正确的一半。仅检查差异的符号：不基于差异的大小尝试插值搜索。你的任务是编写一个程序，给定一组升序和一个键，在排序列表中找到一个特定的位置。

输入

输入包含一个总数（N <= 5000000）和一个查找键，后跟一个包含整数升序集的行。 

输出

如果在排序列表中找到键，则输出在排序列表中包含postion，否则输出-1。

其实本题很简单，但是有坑点，时间控制的特别紧，用C++语法做就会报TLE（题目原意还是主要想卡算法的时间，没想到卡到函数上去了，真实失策呀），数组申请稍微过大就会RE ，所以最后，一切回归原始，废话不多说，上代码走着

#include"stdio.h"
#include"cmath"
#include"algorithm"
using namespace std;
int BinarySerach(int num,int a[],int key)
{
	int m;
	int l = 0;
	int r = num - 1;
	while(l<=r)
	{
		m = (l+r)/2;
		if(key == a[m])
			return m + 1;
		else if(key < a[m])
			r = m - 1;
		else
			l = m + 1;
	}
	return -1;
}
int main()
{
	int num;
	int key;
	scanf("%d %d",&num,&key);
	int a[num]; //开太大了会报RE
	
	for(int i = 0; i < num; i++)
	{
		scanf("%d",&a[i]);
	}

	printf("%d\n",BinarySerach(num,a,key));
	return 0;
}