查找——二分法查找

条件：在非降序排列的数组中查找元素key

返回值：如果找到，返回对应的索引；如果没找到，返回-1；

int BinarySearch(int a[],int n,int key)
{
int left = 0; //左游标
int right = n-1;  //右游标
int middle;
while(left <= right)  //left=right=middle，只有一个元素，这时仍需要比较middle和key
    {
        middle=(left+right)/2;
if(key == a[middle])  //直接找到了
        {
return middle;
        }
else if(key > a[middle])  //key在右半部分，将左游标滑至middle的下一位
        {
            left = middle+1;
        }
else  //key在左半部分，将右游标滑至middle的上一位
        {
            right = middle-1;
        }
    }
return -1;  //游标错位，数组遍历完成，key不存在于数组中
}