二分查找法例题
二分查找法（Binary Search），也称折半查找法，是一种基于比较目标值和数组中间值的查找算法。相比于简单查找法的平均时间复杂度O(n)，二分查找法的平均时间复杂度可以降低至O(log n)。
下面，我们将通过一个例题来深入分析二分查找法的实现过程、时间复杂度、优缺点等多个角度。
问题描述
给定一个有序数组，查找其中是否包含目标值，并返回其索引。若数组中不包含目标值，则返回-1。
例如，给定数组nums=[-10, -2, 0, 3, 7, 9, 15]和目标值target=3，则应返回索引3。
实现过程
二分查找法的实现过程可以分为以下几个步骤：
1. 初始化left为数组首索引0，right为数组尾索引n-1
2. 取数组中间索引mid=(left+right)/2
3. 比较目标值target与当前位置值nums[mid]的大小
4. 若相等，返回mid
5. 若target小于nums[mid]，则在左侧区间[left, mid-1]中继续查找
6. 若target大于nums[mid]，则在右侧区间[mid+1, right]中继续查找
7. 若left > right，则返回-1，表示数组中不包含目标值
时间复杂度
二分查找法的时间复杂度可以用递归树来分析，每次划分区间后问题规模减半，因此深度为O(logn)，每层的操作次数为1，因此时间复杂度为O(logn)。
优缺点
二分查找法的主要优点是时间复杂度低，对于大规模数据查找效率高，而且对于已排好序的数据，二分查找的效率更高。
但是，二分查找法要求数据必须为有序且静态，在数据动态更新的情况下需要维护有序性，这增加了额外的开销。而且，如果数据存储在磁盘等外部存储器上，每次存取数据的时间为定值B，那么二分查找的效率会大大降低。
代码实现
可以使用递归或迭代方法来实现二分查找法。
递归方法：
```
int binarySearch(vector
if (left > right) return -1;
int mid = (left + right) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] > target) return binarySearch(nums, target, left, mid-1);
else return binarySearch(nums, target, mid+1, right);
}
int search(vector
return binarySearch(nums, target, 0, nums.size()-1);
}
```
迭代方法：
```
int search(vector
int left = 0, right = nums.size()-1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] > target) right = mid-1;
else left = mid+1;
}
return -1;
}
```
