【算法面试】二分查找：如何在有序数组中高效搜索目标值

目录

题目描述

示例 1:

示例 2:

问题分析

解决方法

方法 1：标准二分查找

方法 2：递归二分查找

方法 3：非递归简化版本

方法 4：带调试信息的版本

详细步骤

总结

博主v：XiaoMing_Java

---

二分查找是一种常见的算法，广泛应用于计算机科学领域。它的原理是通过不断将目标区间对半划分，从而迅速缩小查找范围。这种方法非常适用于在有序数组中查找特定元素。本篇文章详细解析了如何在有序整型数组中使用二分查找算法来查找目标值，并提供多个代码示例来帮助理解。

题目描述

假设你有一个包含 n 个元素的升序整型数组 nums，以及一个目标值 target。你需要编写一个函数，在数组 nums 中搜索 target，如果目标值存在则返回其下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9

输出: 4

解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2

输出: -1

解释: 2 不存在 nums 中因此返回 -1

问题分析

二分查找法利用了数组已经排好序（升序）的性质，通过每次将查找范围缩小一半，从而极大地提高了查找效率。算法的核心思想如下：

1. 选择数组的中间元素作为比较对象。
2. 如果中间元素正好等于目标值，则直接返回该元素的下标。
3. 否则，如果目标值小于中间元素，则只需在左半部分继续查找；反之，则在右半部分查找。
4. 重复上述过程，直到找到目标值或查找范围为空。

解决方法

方法 1：标准二分查找

以下是实现二分查找的一种标准方法：

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2; // 防止溢出
        int x = nums[mid];
        
        if (x == target) {
            return mid;
        } else if (x > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

方法 2：递归二分查找

除了迭代方式，我们还可以采用递归方式实现二分查找：

public int search(int[] nums, int target) {
    return binarySearch(nums, target, 0, nums.length - 1);
}
private int binarySearch(int[] nums, int target, int left, int right) {
    if (left > right) {
        return -1;
    }
    
    int mid = left + (right - left) / 2; // 防止溢出
    int x = nums[mid];
    
    if (x == target) {
        return mid;
    } else if (x > target) {
        return binarySearch(nums, target, left, mid - 1);
    } else {
        return binarySearch(nums, target, mid + 1, right);
    }
}

方法 3：非递归简化版本

有时我们可以进一步简化代码，使其更简洁：

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        
        if (nums[mid] == target) {
            return mid;
        }
        
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

方法 4：带调试信息的版本

为了更好地理解算法，可以添加调试信息来跟踪程序执行过程：

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        System.out.println("Left: " + left + ", Mid: " + mid + ", Right: " + right);
        if (nums[mid] == target) {
            System.out.println("Found target at index: " + mid);
            return mid;
        }
        
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    System.out.println("Target not found.");
    return -1;
}

详细步骤

1. 初始化：设置 left 为数组的起始索引 0，right 为数组的末尾索引 n-1。
2. 计算中点：在每个迭代中，计算中点 mid 的索引，避免直接加和可能导致的溢出。
3. 比较中点值：将中点值与目标值 target 比较：
   • 若相等，返回中点索引。
   • 若中点值大于目标值，将 right 更新为 mid - 1。
   • 若中点值小于目标值，将 left 更新为 mid + 1。
4. 重复操作：继续上述步骤直到 left 超过 right，表示目标值不在数组中，返回 -1。

总结

二分查找是一种高效的查找算法，其时间复杂度为 O(log n)，非常适用于大规模有序数组的查找任务。通过本文展示的多种实现方法，你可以灵活选择适合自己场景的实现方式。此外，理解并掌握二分查找的基本原理和细节，将会对提升你的编码能力和解决问题的效率大有裨益。希望这些方法能够帮助你顺利解决 java.util.concurrent.BrokenBarrierException 问题，确保程序顺利运行。

如果本文对你有帮助 欢迎 关注、点赞、收藏、评论！！！

博主v：XiaoMing_Java

 📫作者简介：嗨，大家好，我是 小 明（小明java问道之路），互联网大厂后端研发专家，2022博客之星TOP3 / 博客专家 / CSDN后端内容合伙人、InfoQ(极客时间)签约作者、阿里云签约博主、全网5万粉丝博主。

---

🍅 文末获取联系 🍅  👇🏻 精彩专栏推荐订阅收藏 👇🏻

专栏系列（点击解锁）	学习路线（点击解锁）	知识定位
🔥Redis从入门到精通与实战🔥	Redis从入门到精通与实战	围绕原理源码讲解Redis面试知识点与实战
🔥MySQL从入门到精通🔥	MySQL从入门到精通	全面讲解MySQL知识与企业级MySQL实战
🔥计算机底层原理🔥	深入理解计算机系统CSAPP	以深入理解计算机系统为基石，构件计算机体系和计算机思维
	Linux内核源码解析	围绕Linux内核讲解计算机底层原理与并发
🔥数据结构与企业题库精讲🔥	数据结构与企业题库精讲	结合工作经验深入浅出，适合各层次，笔试面试算法题精讲
🔥互联网架构分析与实战🔥	企业系统架构分析实践与落地	行业最前沿视角，专注于技术架构升级路线、架构实践
	互联网企业防资损实践	互联网金融公司的防资损方法论、代码与实践
🔥Java全栈白宝书🔥	精通Java8与函数式编程	本专栏以实战为基础，逐步深入Java8以及未来的编程模式
	深入理解JVM	详细介绍内存区域、字节码、方法底层，类加载和GC等知识
	深入理解高并发编程	深入Liunx内核、汇编、C++全方位理解并发编程
	Spring源码分析	Spring核心七IOC/AOP等源码分析
	MyBatis源码分析	MyBatis核心源码分析
	Java核心技术	只讲Java核心技术