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; }
二分查找时间复杂度：O(log2n)
二叉搜索树时间复杂度： O(log2n)到O(n)，最好情况平衡树，最坏情况单枝树。
