二分查找的叙述正确的是

二分查找（Binary Search），也称折半查找，是一种常用的查找算法。它的基本思想是将有序数列（一般是数组）的中间位置的数与要查找的元素进行比较，如果相等则直接返回该位置，否则根据排序的规则判断要查找的元素在中间位置的左半部分还是右半部分，然后递归地在相应的半部分中执行查找，直到找到要查找的元素或所查找的范围为空。

一般情况下，使用二分查找算法都需要满足以下两个条件：

1. 数组必须是有序的。

2. 数组必须支持随机访问，因为需要定位中间位置。

接下来，我们从多个角度分析二分查找的正确性。

时间复杂度

二分查找算法的时间复杂度是O(logN)，其中N为数组元素个数。对于一个有N个元素的数组，二分查找算法最多只需要执行logN次查找。

空间复杂度

二分查找算法的空间复杂度是O(1)，因为它只需要常数级别的额外空间来存储一些中间变量。

正确性证明

对于一个有序数列a[0], a[1],…, a[n-1]，首先我们需要考虑查找元素x是否在数列中出现过。

对左侧界i和右侧界j，我们假设在查找开始的时候，有如下的关系：i <= j。我们通过不断缩小区间[i, j]的范围，直到找到元素x或者区间为空。

1. 每次查找中，我们首先计算mid = (i + j) / 2。

2. 判断a[mid]是否等于x，如果是直接返回mid位置。

3. 如果a[mid] > x，说明x只可能在左边的区间[i, mid-1]中，缩小右侧界j的范围，令j = mid - 1。

4. 如果a[mid] < x，说明x只可能在右边的区间[mid+1, j]中，缩小左侧界i的范围，令i = mid + 1。

5. 不断缩小查找区间的范围，直到区间为空，即i > j，此时返回查找失败，x不在数组a中出现。

通过这样的二分查找算法，我们可以在时间复杂度为O(logN)的情况下，快速地找到数组中指定元素的位置。

二分查找算法的优缺点与应用场景

1. 优点

（1）相对于数组线性查找，二分查找的时间复杂度更低。

（2）相对于哈希查找，二分查找不需要额外的哈希表，更加节省空间。

2. 缺点

（1）对于非随机性的数据，二分查找的性能会降低，甚至退化为线性查找算法。

（2）二分查找只适用于静态数据，对于动态数据的插入和删除操作，每次操作都需要重新排序，效率低下。

3. 应用场景

二分查找算法适用于对于有序数列进行查找的情况，例如：

（1）查找一段数列中的中位数或者第k个最小值。

（2）查找一个有序数组中值按绝对值排序的索引。

（3）在一个半有序的数列中查找元素。