二分查找法例题

二分查找法（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 & nums, int target, int left, int right) {

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 & nums, int target) {

return binarySearch(nums, target, 0, nums.size()-1);

}

```

迭代方法：

```

int search(vector & nums, int target) {

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;

}

```