二分查找法（Binary Search）详解

博主：情天
发布时间：2024 年 07 月 19 日
1337 次浏览
3 条评论
2300字数
分类：笔记

# 二分查找法（Binary Search）详解

## 引言

二分查找法（Binary Search）是一种高效的查找算法，适用于在有序数组中查找特定元素。与线性查找相比，二分查找的时间复杂度为 $O(\log n)$，这使得它在大数据量的情况下能显著提高查找速度。

## 二分查找法的基本原理

二分查找法通过将查找范围逐步减半来找到目标元素。具体步骤如下：

1. **确定查找范围**：初始时，查找范围是整个数组。
2. **计算中间位置**：找到当前查找范围的中间位置。
3. **比较中间值与目标值**：

* 如果中间值等于目标值，则查找成功，返回中间值的下标。
    * 如果中间值小于目标值，则目标值只可能出现在中间值右边的子数组中。
    * 如果中间值大于目标值，则目标值只可能出现在中间值左边的子数组中。
4. **缩小查找范围**：根据比较结果，调整查找范围为左边或右边的子数组，重复步骤2和3，直到找到目标值或查找范围为空。

## 二分查找法的实现

下面是一个使用二分查找法在有序数组中查找特定值的Java示例代码：

```java
public class BinarySearchExample {

/**
     * 二分查找法
     */
    public static void MyBinarySearch() {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int number = 7;

int max = arr.length - 1;
        int min = 0;
        int index = -1;

while (min <= max) {
            int mid = (max + min) >> 1;  // 右移一位，相当于 (max + min) / 2
            if (arr[mid] > number) {
                max = mid - 1;
            } else if (arr[mid] < number) {
                min = mid + 1;
            } else {
                index = mid;
                break;
            }
        }

if (index >= 0) {
            System.out.println("已通过二分查找法找到对应值, index = " + index);
        } else {
            System.out.println("数组中没有要查找的值, index = " + index);
        }
    }

public static void main(String[] args) {
        MyBinarySearch();
    }
}
```

## 代码解析

1. **初始化变量**：

* `arr`：待查找的有序数组。
    * `number`：要查找的目标值。
    * `max`：数组的最大索引。
    * `min`：数组的最小索引。
    * `index`：用于存储查找到的元素的索引，初始化为-1表示未找到。
2. **循环查找**：

* 使用`while`循环不断缩小查找范围，直到`min`大于`max`。
    * 计算中间索引`mid`：通过 `(max + min) >> 1` 计算中间位置。
    * 比较中间值`arr[mid]`与目标值`number`：

* 如果`arr[mid]`大于目标值，调整`max`为`mid - 1`。
      * 如果`arr[mid]`小于目标值，调整`min`为`mid + 1`。
      * 如果`arr[mid]`等于目标值，设置`index`为`mid`并跳出循环。
3. **输出结果**：

* 根据`index`的值判断是否找到目标值，并输出相应的提示信息。

## 二分查找法的优缺点

### 优点

1. **高效**：时间复杂度为 $O(\log n)$，远优于线性查找的 $O(n)$。
2. **简单实现**：代码简洁易懂。

### 缺点

1. **仅适用于有序数组**：在使用二分查找之前，必须确保数组是有序的。
2. **插入和删除操作复杂**：虽然查找效率高，但在插入和删除元素时需要保持数组有序，可能会带来额外的开销。