二进制搜索（Binary Search）是一种高效的查找算法，适用于 有序数组的快速检索。其核心思想是通过 分治法将搜索范围逐步缩小一半，从而显著提高查找效率。以下是具体解析：
一、基本原理
前提条件 ：数组必须是有序的（升序或降序）。核心步骤
- 从数组的中间元素开始比较目标值。
- 若目标值等于中间元素，则查找成功。
- 若目标值小于中间元素，则在左半部分继续查找。
- 若目标值大于中间元素，则在右半部分继续查找。
- 重复上述过程，每次将搜索范围缩小一半。
二、时间复杂度
最优时间复杂度：
O（log n），其中n是数组长度。每次比较后搜索范围减半，效率远高于线性搜索的O（n）。
最坏时间复杂度：O（log n），前提是数组必须有序。
三、实现示例（伪代码）
```pseudo
BinarySearch(Array, key):
low = 0
high = length(Array) - 1
while low ≤ high:
mid = (low + high) / 2
if Array[mid] == key:
return mid // 查找成功
else if Array[mid] < key:
low = mid + 1 // 在右半部分查找
else:
high = mid - 1 // 在左半部分查找
return -1 // 查找失败
```
四、注意事项
数组需排序：
二分搜索仅适用于有序数组，若数组未排序，需先进行排序（如使用快速排序、归并排序等）。
整数溢出问题：
在某些编程语言中，直接计算`（low + high） / 2`可能导致整数溢出。建议使用`low + （high - low） / 2`来避免此问题。
五、应用场景
数据库查询：数据库中的索引机制常采用二分搜索优化查询速度。
计算机底层：CPU指令集（如x86的`MOVZX`指令）和硬件设计均基于二进制操作。
其他场景：有序文件的查找、字典实现等。
总结
二进制搜索通过分治策略将搜索范围对半划分，适用于大规模数据的快速查找。其效率优势使其成为计算机科学中经典且广泛应用的算法之一。