【超详细】二分查找（折半查找）核心知识点全解析（含多场景代码实现）

一、前言

二分查找（Binary Search）是算法领域最经典、最高效的查找算法之一，其时间复杂度为 O(logn)，相比顺序查找的 O(n) 效率提升呈指数级。它是「分治思想」的典型应用，也是面试中高频考察的算法考点。本文将从核心概念、底层原理、多场景代码实现、边界处理、面试题实战、生活场景应用等维度，帮你彻底掌握二分查找的精髓，解决新手最头疼的「边界越界」「找不到目标值」等问题。

二、二分查找核心概念

2.1 定义

二分查找是一种针对有序的、连续存储的线性数据集（如数组）的高效查找算法。它通过不断将查找区间折半，缩小查找范围，直到找到目标值或确定目标值不存在。

2.2 核心前提（缺一不可）

1. 数据有序：必须是升序或降序排列（本文以升序为例）；
2. 随机访问：数据需存储在支持随机访问的结构中（如数组，链表不适用，因为链表随机访问复杂度为 O(n)，会抵消二分查找的优势）；
3. 无重复 / 可处理重复：基础版处理无重复数据，进阶版可处理重复数据的边界查找。

2.3 核心思想（分治）

1. 确定查找区间的左边界（left）和右边界（right）；
2. 计算区间的中间位置（mid），获取中间值nums[mid]；
3. 比较nums[mid]与目标值target：
   • 若nums[mid] == target：找到目标值，返回 mid；
   • 若nums[mid] > target：目标值在左半区间，调整右边界为mid - 1；
   • 若nums[mid] < target：目标值在右半区间，调整左边界为mid + 1；
4. 重复步骤 2-3，直到left > right（区间为空，目标值不存在）。

三、二分查找执行流程（可视化）

以升序数组[1,3,5,7,9,11,13]查找目标值7为例：

初始区间：left=0, right=6 → mid=(0+6)/2=3 → nums[3]=7 == target → 找到，返回3 若查找目标值 `5`： 第1轮：left=0, right=6 → mid=3 → nums[3]=7 > 5 → right=2 第2轮：left=0, right=2 → mid=1 → nums[1]=3 < 5 → left=2 第3轮：left=2, right=2 → mid=2 → nums[2]=5 == target → 返回2 若查找目标值 `4`（不存在）： 第1轮：left=0, right=6 → mid=3 → 7>4 → right=2 第2轮：left=0, right=2 → mid=1 → 3<4 → left=2 第3轮：left=2, right=2 → mid=2 →5>4 → right=1 此时 left=2 > right=1 → 区间为空，返回-1

四、多场景代码实现（Java 版）

4.1 基础版：查找目标值是否存在（无重复数据）

最常用的基础版本，找到返回索引，未找到返回 - 1。

核心：区间定义为「左闭右闭」[left, right]，终止条件left > right。

/** * 二分查找基础版（左闭右闭区间 [left, right]） * @param nums 升序无重复数组 * @param target 目标值 * @return 目标值索引，未找到返回-1 */ public class BinarySearchBasic { public static int binarySearch(int[] nums, int target) { // 1. 处理边界：数组为空或长度为0 if (nums == null || nums.length == 0) { return -1; } // 2. 初始化左右边界（左闭右闭） int left = 0; int right = nums.length - 1; // 3. 循环查找：区间不为空（left <= right） while (left <= right) { // 计算mid：避免 (left + right) 溢出，等价于 (left + right) / 2 int mid = left + (right - left) / 2; if (nums[mid] == target) { // 找到目标值，返回索引 return mid; } else if (nums[mid] > target) { // 目标值在左半区间，缩小右边界 right = mid - 1; } else { // 目标值在右半区间，缩小左边界 left = mid + 1; } } // 区间为空，未找到目标值 return -1; } // 测试 public static void main(String[] args) { int[] nums = {1,3,5,7,9,11,13}; System.out.println(binarySearch(nums, 7)); // 输出3 System.out.println(binarySearch(nums, 5)); // 输出2 System.out.println(binarySearch(nums, 4)); // 输出-1 } }

4.2 左边界版：查找第一个等于目标值的索引（含重复数据）

适用于数组有重复元素，需找到「第一个出现」的目标值（如[1,2,2,2,3]找第一个2，返回 1）。

/** * 二分查找左边界版（找第一个等于target的索引） * @param nums 升序有重复数组 * @param target 目标值 * @return 第一个目标值索引，未找到返回-1 */ public class BinarySearchLeftBound { public static int leftBoundBinarySearch(int[] nums, int target) { if (nums == null || nums.length == 0) { return -1; } int left = 0; int right = nums.length - 1; // 记录左边界，初始为-1（未找到） int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { // 找到目标值，不直接返回，继续向左找更小的索引 result = mid; right = mid - 1; } else if (nums[mid] > target) { right = mid - 1; } else { left = mid + 1; } } return result; } // 测试 public static void main(String[] args) { int[] nums = {1,2,2,2,3,4,5}; System.out.println(leftBoundBinarySearch(nums, 2)); // 输出1 System.out.println(leftBoundBinarySearch(nums, 6)); // 输出-1 } }

4.3 右边界版：查找最后一个等于目标值的索引（含重复数据）

适用于数组有重复元素，需找到「最后一个出现」的目标值（如[1,2,2,2,3]找最后一个2，返回 3）。

/** * 二分查找右边界版（找最后一个等于target的索引） * @param nums 升序有重复数组 * @param target 目标值 * @return 最后一个目标值索引，未找到返回-1 */ public class BinarySearchRightBound { public static int rightBoundBinarySearch(int[] nums, int target) { if (nums == null || nums.length == 0) { return -1; } int left = 0; int right = nums.length - 1; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { // 找到目标值，不直接返回，继续向右找更大的索引 result = mid; left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else { left = mid + 1; } } return result; } // 测试 public static void main(String[] args) { int[] nums = {1,2,2,2,3,4,5}; System.out.println(rightBoundBinarySearch(nums, 2)); // 输出3 System.out.println(rightBoundBinarySearch(nums, 6)); // 输出-1 } }

4.4 变种版：查找大于 / 小于目标值的第一个元素

4.4.1 查找大于 target 的第一个元素

/** * 查找大于target的第一个元素索引 * @param nums 升序数组 * @param target 目标值 * @return 第一个大于target的元素索引，无则返回数组长度 */ public class BinarySearchGreater { public static int findFirstGreater(int[] nums, int target) { if (nums == null || nums.length == 0) { return 0; } int left = 0; int right = nums.length - 1; // 初始值设为数组长度（表示无大于target的元素） int result = nums.length; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] > target) { // 找到更大的元素，记录索引并向左找更小的索引 result = mid; right = mid - 1; } else { // 元素小于等于target，向右找 left = mid + 1; } } return result; } // 测试 public static void main(String[] args) { int[] nums = {1,3,5,7,9,11}; System.out.println(findFirstGreater(nums, 6)); // 输出3（nums[3]=7>6） System.out.println(findFirstGreater(nums, 11)); // 输出6（无大于11的元素） } }

五、二分查找的优缺点 & 适用场景

适用场景

1. 静态数据集（无频繁增删）的高效查找；
2. 有序数组的精准查找、边界查找；
3. 数值范围查找（如 x 的平方根、猜数字大小）；
4. 算法题中的优化手段（如将暴力枚举的 O(n) 优化为 O(logn)）。

六、经典面试题实战（附思路 + 代码）

6.1 题目 1：x 的平方根（LeetCode 69）

题目描述：计算并返回 x 的平方根，结果只保留整数部分（如 x=8，返回 2）。思路：二分查找范围[0, x]，找最大的 mid 满足mid*mid <= x。

public class SqrtX { public static int mySqrt(int x) { if (x == 0 || x == 1) { return x; } int left = 1; int right = x; int result = 0; while (left <= right) { int mid = left + (right - left) / 2; // 避免 mid*mid 溢出，改用除法 if (mid <= x / mid) { result = mid; left = mid + 1; } else { right = mid - 1; } } return result; } public static void main(String[] args) { System.out.println(mySqrt(8)); // 输出2 System.out.println(mySqrt(16)); // 输出4 } }

6.2 题目 2：搜索旋转排序数组（LeetCode 33）
题目描述：升序数组在某点旋转（如 [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]），查找目标值，要求时间复杂度 O(logn)。

public class SearchRotatedArray { public static int search(int[] nums, int target) { if (nums == null || nums.length == 0) { return -1; } int left = 0; int right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } // 左半部分有序 if (nums[left] <= nums[mid]) { // 目标值在左半有序区间 if (nums[left] <= target && target < nums[mid]) { right = mid - 1; } else { left = mid + 1; } } else { // 右半部分有序 if (nums[mid] < target && target <= nums[right]) { left = mid + 1; } else { right = mid - 1; } } } return -1; } public static void main(String[] args) { int[] nums = {4,5,6,7,0,1,2}; System.out.println(search(nums, 0)); // 输出4 System.out.println(search(nums, 3)); // 输出-1 } }

7.1 场景 1：猜数字游戏（1-100）

7.1.1 场景描述

你心里想一个 1-100 之间的整数，程序通过二分查找的方式「猜数字」，每次你告诉程序 “猜大了”“猜小了” 或 “猜对了”，程序最终快速找到目标数字（相比顺序猜 1、2、3… 效率提升数十倍）。

7.1.2 解决思路

• 初始查找区间：left=1，right=100；
• 每次猜区间中点mid，根据用户反馈调整边界：
  • 反馈 “大了”：目标在左半区间，right = mid - 1；
  • 反馈 “小了”：目标在右半区间，left = mid + 1；
  • 反馈 “对了”：结束查找，输出结果。

7.1.3 Java 代码实现

import java.util.Scanner; /** * 生活场景1：二分查找实现1-100猜数字游戏 */ public class GuessNumberGame { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.println("===== 猜数字游戏 ====="); System.out.println("请心里想一个1-100之间的整数，我将用二分法猜出来！"); System.out.println("每次我猜完后，请输入反馈："); System.out.println(" 1 → 我猜大了； 2 → 我猜小了； 3 → 猜对了"); int left = 1; int right = 100; int guessCount = 0; // 记录猜测次数 while (left <= right) { guessCount++; int mid = left + (right - left) / 2; System.out.println("\n我猜数字是：" + mid); System.out.print("请输入你的反馈（1/2/3）："); int feedback = scanner.nextInt(); if (feedback == 3) { System.out.println("太棒了！我用了" + guessCount + "次猜对了，目标数字是" + mid); break; } else if (feedback == 1) { // 猜大了，缩小右边界 right = mid - 1; System.out.println("哦，猜大了，我继续缩小范围..."); } else if (feedback == 2) { // 猜小了，缩小左边界 left = mid + 1; System.out.println("哦，猜小了，我继续缩小范围..."); } else { System.out.println("输入无效，请输入1、2或3！"); guessCount--; // 无效输入不计入次数 } } // 理论上1-100最多7次就能猜对（2^7=128>100） if (left > right) { System.out.println("你是不是谎报反馈了？我找不到这个数字😜"); } scanner.close(); } }

7.2 场景 2：图书馆按页码找书籍位置

7.2.1 场景描述

图书馆的书架上按「书籍页码范围」有序摆放书籍（比如：书 1 对应页码 1-50、书 2 对应 51-100、书 3 对应 101-150…），现在要找包含目标页码（如 88 页）的书在书架上的位置，用二分查找快速定位。

7.2.2 解决思路

• 定义Book类，包含「书籍编号、起始页码、结束页码」；
• 将书籍数组按「起始页码」升序排列（满足二分查找的有序前提）；
• 二分查找目标页码：判断mid位置书籍的页码区间是否包含目标页码，不包含则调整边界。

7.2.3 Java 代码实现

/** * 书籍实体类：包含编号、起始页码、结束页码 */ class Book { private int bookId; // 书籍编号（对应书架位置） private int startPage; // 起始页码 private int endPage; // 结束页码 public Book(int bookId, int startPage, int endPage) { this.bookId = bookId; this.startPage = startPage; this.endPage = endPage; } // getter方法 public int getBookId() { return bookId; } public int getStartPage() { return startPage; } public int getEndPage() { return endPage; } } /** * 生活场景2：图书馆按页码找书籍位置（二分查找实现） */ public class FindBookByPage { /** * 查找包含目标页码的书籍编号 * @param books 有序的书籍数组（按startPage升序） * @param targetPage 目标页码 * @return 书籍编号，未找到返回-1 */ public static int findBook(Book[] books, int targetPage) { if (books == null || books.length == 0) { return -1; } int left = 0; int right = books.length - 1; while (left <= right) { int mid = left + (right - left) / 2; Book midBook = books[mid]; if (targetPage >= midBook.getStartPage() && targetPage <= midBook.getEndPage()) { // 目标页码在当前书籍的区间内，找到 return midBook.getBookId(); } else if (targetPage < midBook.getStartPage()) { // 目标页码更小，找左半区间 right = mid - 1; } else { // 目标页码更大，找右半区间 left = mid + 1; } } // 未找到包含目标页码的书籍 return -1; } public static void main(String[] args) { // 模拟图书馆书架：5本书，按起始页码升序排列 Book[] books = { new Book(1, 1, 50), new Book(2, 51, 100), new Book(3, 101, 150), new Book(4, 151, 200), new Book(5, 201, 250) }; // 测试1：找88页的书（应返回2） int targetPage1 = 88; int bookId1 = findBook(books, targetPage1); System.out.println("页码" + targetPage1 + "对应的书籍编号：" + bookId1); // 输出2 // 测试2：找155页的书（应返回4） int targetPage2 = 155; int bookId2 = findBook(books, targetPage2); System.out.println("页码" + targetPage2 + "对应的书籍编号：" + bookId2); // 输出4 // 测试3：找300页的书（无，返回-1） int targetPage3 = 300; int bookId3 = findBook(books, targetPage3); System.out.println("页码" + targetPage3 + "对应的书籍编号：" + bookId3); // 输出-1 } }

7.3 场景 3：快递站按编号找包裹位置

7.3.1 场景描述

快递站的货架上按「包裹编号」升序摆放包裹（比如货架 1=1001、货架 2=1002、货架 3=1003… 货架 100=1100），现在要找目标编号的包裹在哪个货架，用二分查找替代逐个查找，提升效率。

7.3.2 解决思路

• 包裹编号数组是升序的（满足二分查找前提）；
• 二分查找目标编号，找到后返回「索引 + 1」（对应货架号）；
• 未找到则返回 - 1，表示无该包裹。

7.3.3 Java 代码实现

/** * 生活场景3：快递站按编号找包裹的货架位置（二分查找实现） */ public class FindPackageByNumber { /** * 查找目标包裹编号对应的货架位置 * @param packageNums 升序的包裹编号数组（索引=货架号-1） * @param targetNum 目标包裹编号 * @return 货架号（索引+1），未找到返回-1 */ public static int findPackageShelf(int[] packageNums, int targetNum) { if (packageNums == null || packageNums.length == 0) { return -1; } int left = 0; int right = packageNums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (packageNums[mid] == targetNum) { // 找到，返回货架号（索引+1） return mid + 1; } else if (packageNums[mid] > targetNum) { // 包裹编号更大，找左半区间 right = mid - 1; } else { // 包裹编号更小，找右半区间 left = mid + 1; } } // 未找到目标包裹 return -1; } public static void main(String[] args) { // 模拟快递站包裹编号：1001-1100，对应货架1-100 int[] packageNums = new int[100]; for (int i = 0; i < 100; i++) { packageNums[i] = 1001 + i; } // 测试1：找编号1050的包裹（应返回50） int target1 = 1050; int shelf1 = findPackageShelf(packageNums, target1); System.out.println("包裹" + target1 + "在货架：" + shelf1); // 输出50 // 测试2：找编号1088的包裹（应返回88） int target2 = 1088; int shelf2 = findPackageShelf(packageNums, target2); System.out.println("包裹" + target2 + "在货架：" + shelf2); // 输出88 // 测试3：找编号1200的包裹（无，返回-1） int target3 = 1200; int shelf3 = findPackageShelf(packageNums, target3); System.out.println("包裹" + target3 + "在货架：" + shelf3); // 输出-1 } }

八、总结

核心要点回顾

1. 核心前提：二分查找仅适用于有序、支持随机访问的数据集（优先数组）；
2. 区间定义：新手优先用「左闭右闭[left, right]」，终止条件left > right，mid 计算用left + (right - left)/2避免溢出；
3. 边界处理：
   • 找第一个目标值：找到后继续向左缩边界（right = mid - 1）；
   • 找最后一个目标值：找到后继续向右缩边界（left = mid + 1）；
4. 时间复杂度：稳定的 O(logn)，是二分查找的核心优势；
5. 生活应用：只要满足「数据有序、可折半缩小范围」，就能用二分思想提升效率（如猜数字、找书籍、找快递）。

学习建议

1. 先掌握基础版，再攻克边界版和变种版，重点理解「缩边界」的逻辑；
2. 手动模拟执行流程（如在纸上画区间变化），解决「边界越界」问题；
3. 尝试将生活中的查找场景转化为二分查找（如找价格区间、找楼层），加深对思想的理解；
4. 刷 LeetCode 二分查找专题（标签：二分查找），从简单到中等难度，巩固实战能力。

文末小结：二分查找的核心不是「写代码」，而是「分治思想」—— 将大问题拆分为小问题，通过折半快速缩小范围。无论是编程算法还是日常生活，只要抓住「有序」和「折半」两个核心，就能用二分思想解决问题，大幅提升效率。建议多写、多测、多模拟，让二分查找成为你的「通用高效工具」。