#include <cstdio>  /*   * 传统的二分查找，数组有序且没有重复   */  int binary_S(int *a, int n, int key)  {      int l = 0, r = n-1;      int mid;      while (l <= r){          mid = (l + r) >> 1;          if (a[mid] == key)              return mid;          if (a[mid] > key)              r = mid - 1;          else              l = mid + 1;      }      return -1;  }  /*   * 找出等于key且下标最小的值的下标，输入数组有序   */  int binary_S2(int *a, int n, int key)  {      int l = 0, r = n-1;      while (l < r){          int mid = (l + r) >> 1;          if (a[mid] >= key)              r = mid;          else              l = mid + 1;      }      if (a[r] == key)          return r;      return -1;  }  /*   * 找出等于key且下标最大的值的下标，输入数组有序   */  int binary_S3(int *a, int n, int key)  {      int l = 0, r = n-1;      while (l < r){          int mid = (l + r + 1) >> 1;          if (a[mid] <= key)              l = mid;          else              r = mid - 1;      }      if (a[l] == key)          return l;      return -1;  }  /*   * 找出一个先递增后递减数列的最大值   */  int binary_S4(int *a, int n)  {      int l = 0, r = n-1;      int mid;      while (l <= r){          mid = (l + r) >> 1;          if (mid > 0 && a[mid-1] > a[mid])              r = mid - 1;          else if (mid < n-1 && a[mid+1] > a[mid])              l = mid + 1;          else              return a[mid];      }  }