折半查找

int BinarySearch(int a[], const int& x, int n) {
  int left = 0;
  int right = n - 1;
  while (left <= right) {//注意是小于等于
    int mid = (left + right) / 2;
    if (a[mid] < x) {//比查找元素小，查找元素在右区间
      left = mid + 1;
    }
    if (a[mid] > x) {
      right = mid - 1;//比查找元素大，查找元素在左区间
    }
    if (a[mid] == x) {
      return mid;
    }
  }
  return -1;
}