编程导航会员会员
登录/注册

一文带你学会"二分查找"

大家好，我是算法学长，一个热爱分享算法知识的开发者。 算法 0 基础、校招冲刺中大厂，推荐使用算法导航：https://algo.codefather.cn/ 交互式算法学习平台，带大家系统化学习算法。

二分查找

介绍

二分查找（Binary Search）是一种高效的查找算法，也叫折半查找。核心思想：对于一个有序的数据集合，每次查找都将查找范围缩小为原来的一半，直到找到目标值或确定目标值不存在。二分查找要求数据必须是有序的，经常应用于数组等支持随机访问的数据结构里。跟线性查找相比，二分查找的效率要高得多，特别是对于大规模数据集。

算法步骤

  1. 确定查找范围的左边界 left 和右边界 right
  2. 计算中间位置 mid = (left + right) / 2（注意整数溢出问题，更安全的做法是 mid = left + (right - left) / 2）
  3. 将中间位置的元素与目标值比较
    • 如果中间元素等于目标值，查找成功，返回中间元素的位置
    • 如果中间元素大于目标值，目标值可能在左半部分，将右边界调整为 mid - 1
    • 如果中间元素小于目标值，目标值可能在右半部分，将左边界调整为 mid + 1
  4. 重复步骤2-3，直到找到目标值或者左边界大于右边界（此时表示目标值不存在）

核心特性

  • 要求有序：二分查找只适用于有序数据集合
  • 时间复杂度：O(log n)，在大规模数据集上非常高效
  • 空间复杂度：迭代实现为O(1)，递归实现为O(log n)（因为递归调用栈的深度）
  • 随机访问：要求数据结构支持O(1)时间复杂度的随机访问（比如数组）

基础实现

下面是二分查找算法在各种主流编程语言中的实现：

Java实现

▼
java
复制代码
public class BinarySearch {
    // 迭代实现
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            // 避免整数溢出
            int mid = left + (right - left) / 2;
            
            // 找到目标值
            if (arr[mid] == target) {
                return mid;
            }
            // 在左半部分继续查找
            else if (arr[mid] > target) {
                right = mid - 1;
            }
            // 在右半部分继续查找
            else {
                left = mid + 1;
            }
        }
        
        // 未找到目标值
        return -1;
    }
    
    // 递归实现
    public static int binarySearchRecursive(int[] arr, int target, int left, int right) {
        if (left > right) {
            return -1;
        }
        
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            return binarySearchRecursive(arr, target, left, mid - 1);
        } else {
            return binarySearchRecursive(arr, target, mid + 1, right);
        }
    }
    
    // 测试
    public static void main(String[] args) {
        int[] arr = {2, 3, 4, 10, 40, 50, 70, 80};
        int target = 10;
        
        // 迭代方法
        int result = binarySearch(arr, target);
        if (result == -1) {
            System.out.println("元素 " + target + " 不存在于数组中");
        } else {
            System.out.println("元素 " + target + " 在数组中的索引为 " + result);
        }
        
        // 递归方法
        result = binarySearchRecursive(arr, target, 0, arr.length - 1);
        if (result == -1) {
            System.out.println("元素 " + target + " 不存在于数组中");
        } else {
            System.out.println("元素 " + target + " 在数组中的索引为 " + result);
        }
    }
}

JavaScript 实现

▼
javascript
复制代码
// 迭代实现
function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return -1;
}

// 递归实现
function binarySearchRecursive(arr, target, left, right) {
    if (left > right) {
        return -1;
    }
    
    const mid = Math.floor(left + (right - left) / 2);
    
    if (arr[mid] === target) {
        return mid;
    } else if (arr[mid] > target) {
        return binarySearchRecursive(arr, target, left, mid - 1);
    } else {
        return binarySearchRecursive(arr, target, mid + 1, right);
    }
}

// 测试
const arr = [2, 3, 4, 10, 40, 50, 70, 80];
const target = 10;

// 迭代方法
let result = binarySearch(arr, target);
if (result === -1) {
    console.log(`元素 ${target} 不存在于数组中`);
} else {
    console.log(`元素 ${target} 在数组中的索引为 ${result}`);
}

// 递归方法
result = binarySearchRecursive(arr, target, 0, arr.length - 1);
if (result === -1) {
    console.log(`元素 ${target} 不存在于数组中`);
} else {
    console.log(`元素 ${target} 在数组中的索引为 ${result}`);
}

Python 实现

▼
python
复制代码
# 迭代实现
def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            right = mid - 1
        else:
            left = mid + 1
    
    return -1

# 递归实现
def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
    
    mid = left + (right - left) // 2
    
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search_recursive(arr, target, left, mid - 1)
    else:
        return binary_search_recursive(arr, target, mid + 1, right)

# 测试
arr = [2, 3, 4, 10, 40, 50, 70, 80]
target = 10

# 迭代方法
result = binary_search(arr, target)
if result == -1:
    print(f"元素 {target} 不存在于数组中")
else:
    print(f"元素 {target} 在数组中的索引为 {result}")

# 递归方法
result = binary_search_recursive(arr, target, 0, len(arr) - 1)
if result == -1:
    print(f"元素 {target} 不存在于数组中")
else:
    print(f"元素 {target} 在数组中的索引为 {result}")

Go 实现

▼
go
复制代码
package main

import "fmt"

// 迭代实现
func binarySearch(arr []int, target int) int {
    left := 0
    right := len(arr) - 1
    
    for left <= right {
        mid := left + (right - left) / 2
        
        if arr[mid] == target {
            return mid
        } else if arr[mid] > target {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    
    return -1
}

// 递归实现
func binarySearchRecursive(arr []int, target, left, right int) int {
    if left > right {
        return -1
    }
    
    mid := left + (right - left) / 2
    
    if arr[mid] == target {
        return mid
    } else if arr[mid] > target {
        return binarySearchRecursive(arr, target, left, mid - 1)
    } else {
        return binarySearchRecursive(arr, target, mid + 1, right)
    }
}

func main() {
    arr := []int{2, 3, 4, 10, 40, 50, 70, 80}
    target := 10
    
    // 迭代方法
    result := binarySearch(arr, target)
    if result == -1 {
        fmt.Printf("元素 %d 不存在于数组中\n", target)
    } else {
        fmt.Printf("元素 %d 在数组中的索引为 %d\n", target, result)
    }
    
    // 递归方法
    result = binarySearchRecursive(arr, target, 0, len(arr) - 1)
    if result == -1 {
        fmt.Printf("元素 %d 不存在于数组中\n", target)
    } else {
        fmt.Printf("元素 %d 在数组中的索引为 %d\n", target, result)
    }
}

C 实现

▼
c
复制代码
#include <stdio.h>

// 迭代实现
int binarySearch(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return -1;
}

// 递归实现
int binarySearchRecursive(int arr[], int target, int left, int right) {
    if (left > right) {
        return -1;
    }
    
    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] > target) {
        return binarySearchRecursive(arr, target, left, mid - 1);
    } else {
        return binarySearchRecursive(arr, target, mid + 1, right);
    }
}

int main() {
    int arr[] = {2, 3, 4, 10, 40, 50, 70, 80};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 10;
    
    // 迭代方法
    int result = binarySearch(arr, n, target);
    if (result == -1) {
        printf("元素 %d 不存在于数组中\n", target);
    } else {
        printf("元素 %d 在数组中的索引为 %d\n", target, result);
    }
    
    // 递归方法
    result = binarySearchRecursive(arr, target, 0, n - 1);
    if (result == -1) {
        printf("元素 %d 不存在于数组中\n", target);
    } else {
        printf("元素 %d 在数组中的索引为 %d\n", target, result);
    }
    
    return 0;
}

C++ 实现

▼
cpp
复制代码
#include <iostream>
#include <vector>

// 迭代实现
int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return -1;
}

// 递归实现
int binarySearchRecursive(const std::vector<int>& arr, int target, int left, int right) {
    if (left > right) {
        return -1;
    }
    
    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] > target) {
        return binarySearchRecursive(arr, target, left, mid - 1);
    } else {
        return binarySearchRecursive(arr, target, mid + 1, right);
    }
}

int main() {
    std::vector<int> arr = {2, 3, 4, 10, 40, 50, 70, 80};
    int target = 10;
    
    // 迭代方法
    int result = binarySearch(arr, target);
    if (result == -1) {
        std::cout << "元素 " << target << " 不存在于数组中" << std::endl;
    } else {
        std::cout << "元素 " << target << " 在数组中的索引为 " << result << std::endl;
    }
    
    // 递归方法
    result = binarySearchRecursive(arr, target, 0, arr.size() - 1);
    if (result == -1) {
        std::cout << "元素 " << target << " 不存在于数组中" << std::endl;
    } else {
        std::cout << "元素 " << target << " 在数组中的索引为 " << result << std::endl;
    }
    
    return 0;
}

优缺点

优点

  • 查找效率非常高，时间复杂度为 O(log n)
  • 在大规模数据集上表现优异
  • 实现相对简单
  • 不需要额外的空间（迭代实现）

缺点

  • 要求数据必须是有序的
  • 只适用于支持随机访问的数据结构（如数组）
  • 对于频繁插入和删除的数据结构，维护有序性的成本很高
  • 不适合小数据量的查找（这种情况下线性查找可能更快）

应用场景

二分查找在很多场景中都有广泛的应用：

  • 数据库索引的实现（如 B 树和 B+ 树的查找过程）
  • 查找最接近某个值的元素（下界查找和上界查找）
  • 计算平方根等数值计算中（二分法求解）
  • 猜数字游戏（每次猜测中间值）
  • 在旋转排序数组中查找元素
  • 查找数组中第一个或最后一个满足某条件的元素

扩展

二分查找的变种

二分查找有许多变种，用来解决不同的问题：

查找第一个等于目标值的元素

▼
java
复制代码
public static int findFirstEqual(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] > target) {
            right = mid - 1;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            // 找到目标值，但需要继续向左查找是否有相同值
            result = mid;
            right = mid - 1;
        }
    }
    
    return result;
}

查找最后一个等于目标值的元素

▼
java
复制代码
public static int findLastEqual(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] > target) {
            right = mid - 1;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            // 找到目标值，但需要继续向右查找是否有相同值
            result = mid;
            left = mid + 1;
        }
    }
    
    return result;
}

查找第一个大于等于目标值的元素（下界）

▼
java
复制代码
public static int lowerBound(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    int result = arr.length; // 如果所有元素都小于target，返回数组长度
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] >= target) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return result;
}

查找最后一个小于等于目标值的元素（上界）

▼
java
复制代码
public static int upperBound(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    int result = -1; // 如果所有元素都大于target，返回-1
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] <= target) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

测验

  1. 二分查找的时间复杂度是多少？为什么它比线性查找更高效？
  2. 二分查找的前提条件是什么？它适用于哪些数据结构？
  3. 为什么计算中间位置时，推荐使用 mid = left + (right - left) / 2 而不是 mid = (left + right) / 2？
  4. 在有重复元素的有序数组中，如何找到目标值的第一次出现位置？
  5. 二分查找的递归实现和迭代实现在空间复杂度上有何区别？

测验答案

  1. O(log n)。因为每次查找都将搜索范围缩小一半，线性查找需要遍历全部元素。
  2. 数据必须有序。适用于支持随机访问的数据结构，如数组。
  3. mid = left + (right - left) / 2 可以避免在处理大数组的时候可能发生的整数溢出问题。如果 left 和 right 都很大，它们的和有可能超过整数类型的最大值。
  4. 找到目标值后不立即返回，记录当前位置，继续在左半部分查找（将 right 设为 mid - 1），直到找不到为止，最后返回记录的位置。
  5. 迭代实现空间复杂度为 O(1)，只需常量级的额外空间；递归实现的空间复杂度为 O(log n)，因为递归调用栈的深度与二分查找的次数成正比。

相关的 LeetCode 热门题目

下面推荐一些可以应用二分查找思想的 LeetCode 题目：

这些题目涵盖了二分查找的各种变形和应用场景，从简单到复杂，对理解和掌握二分查找算法非常有帮助。

学算法就上算法导航：https://algo.codefather.cn/ ，交互式算法学习平台！

算法
0个评论
全部评论
点击登录，快来和大家讨论吧～
表情
图片
暂无评论
算法学长
算法学长
等级vip
内容推荐
更多
最近刷算法的一些心得~
6
Claude Code 源码架构深度解析：1884 个文件背后的 AI 编程工具设计哲学
23
深度解析 Claude Code 记忆系统：从源码看 AI 编程助手如何"记住"你的项目
6
LeetCode Hot 100 二分查找篇 - 每次砍一半，六道题从入门到穿透
2
卷AI、卷算法、2026 年的前端工程师到底在卷什么？
7
作者分享
更多
一文带你学会"最近点对问题"
4
一文带你学会"分治算法"
4
一文带你学会"KMP 算法"
6
一文带你学会"Boyer-Moore算法"
3
一文带你学会"Rabin-Karp算法"
3
下载 APP