二分查找看这篇就够了！Java 版超详细讲解+高频题解

大家好，今天我们来彻底吃透二分查找。作为算法面试、笔试中的“常青树”，它是必考且基础的核心知识点，看似只有“左右指针+中间值对比”这一个简单逻辑，但实际应用中，边界处理、区间收缩、题型变形等细节极易出错，很多人刷题时常常陷入死循环或边界遗漏的困境。今天，我会用Java 语言，从基础原理入手，拆解标准模板，再结合LeetCode高频真题实战演练，一步步带你吃透二分查找，轻松应对各类面试考点。

一、什么是二分查找？

二分查找又称折半查找，是一种高效的查找算法，其核心适用前提有两个：一是数组必须有序（升序或降序均可，本文默认以升序为例），二是数组中无重复元素（有重复元素的场景会在后续边界查找中专门讲解）。

核心思想（通俗解读）：

• 每次查找时，将当前的搜索区间一分为二，锁定中间位置的元素，以此为基准进行判断；

• 通过中间元素与目标值的大小对比，直接舍弃不可能包含目标值的一半区间，无需逐一遍历；

• 仅在剩下的另一半区间中继续重复“分半-判断-舍弃”的流程，直到找到目标值或确定目标值不存在；

• 时间复杂度为 O(log n)（n为数组长度），相较于暴力查找的O(n)，效率提升极为明显，尤其在数据量较大（如n>10000）时，差距会格外突出。

一句话总结：有单调性，就可以二分。这里的单调性不仅指数组整体有序，只要能将搜索区间划分为“满足条件”和“不满足条件”两部分，且两部分边界清晰，就能用二分思想解题。

---

二、最基础模板：LeetCode 704 二分查找

这是二分查找的入门经典题，也是所有二分变形题的基础，吃透这道题，就能掌握二分查找的核心框架，后续的边界查找、真题实战都能以此为基础延伸。

题目

给定一个 n 个元素的有序、无重复整型数组 nums 和一个目标值 target，写一个函数搜索 nums 中的 target。如果目标值存在，返回其下标；如果不存在，返回 -1。（题目链接：LeetCode 704. 二分查找）

Java 代码

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2; // 防止溢出，替代(left+right)/2
            
            if (nums[mid] == target) {
                return mid; // 找到目标值，直接返回下标
            } else if (nums[mid] < target) {
                left = mid + 1; // 目标值在右侧区间，缩小左边界
            } else {
                right = mid - 1; // 目标值在左侧区间，缩小右边界
            }
        }
        return -1; // 循环结束仍未找到，返回-1
    }
}

关键点（避坑重点）

1. 循环条件 left <= right：这里必须包含“等于”，因为当left和right重合时，当前位置的元素还未被判断，若漏掉“等于”，会导致该位置的目标值被遗漏，出现查找失败的错误。

2. mid 不要写成 (left+right)/2：当left和right均为较大的整数（如接近int类型的最大值）时，两者相加会超出int类型的取值范围，导致数值溢出，进而出现计算错误；而left + (right - left)/2 等价于 (left+right)/2，却能有效避免溢出问题。

3. 区间更新必须是 mid+1 / mid-1，否则会死循环：因为当nums[mid]不等于target时，该位置已被排除，若仅更新为left=mid或right=mid，会导致区间无法缩小，陷入无限循环（例如：left=1、right=2，mid=1，若nums[mid]<target，left仍设为1，区间始终不变）。

---

三、二分最重要的能力：找边界

在实际面试中，单纯查找目标值的基础题占比极低，更多的是变形题——找左边界、右边界、插入位置，这类题目核心考察对区间收缩的精准控制，也是二分查找的难点所在，掌握这部分，就能应对80%的二分变形题。

1. 找左边界（第一个等于 target 的位置）

适用场景：数组中存在重复元素，需要找到目标值第一次出现的位置（例如：数组[1,2,2,2,3]，target=2，左边界为1）。

private int leftBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1; // 目标在右侧，左边界右移
        } else {
            right = mid; // 目标在左侧或当前位置，右边界左移（保留mid）
        }
    }
    // 循环结束后left=right，判断该位置是否为目标值
    return nums[left] == target ? left : -1;
}

2. 找右边界（最后一个等于 target 的位置）

适用场景：数组中存在重复元素，需要找到目标值最后一次出现的位置（例如：数组[1,2,2,2,3]，target=2，右边界为3）。

private int rightBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;

    while (left < right) {
        int mid = left + (right - left + 1) / 2; // 向上取整，避免死循环
        if (nums[mid] > target) {
            right = mid - 1; // 目标在左侧，右边界左移
        } else {
            left = mid; // 目标在右侧或当前位置，左边界右移（保留mid）
        }
    }
    // 循环结束后left=right，判断该位置是否为目标值
    return nums[left] == target ? left : -1;
}

记忆口诀（快速掌握，避免混淆）

• 找左边界：mid = 向下取整，right=mid（优先收缩右边界，保留左侧可能的边界）；

• 找右边界：mid = 向上取整，left=mid（优先收缩左边界，保留右侧可能的边界）；

• 循环条件一律用 left < right（循环结束后left与right重合，再判断是否为目标值，避免边界遗漏）。

---

四、LeetCode 高频真题（Java 版）

理论结合实战才是掌握二分的关键，下面精选5道LeetCode高频真题，覆盖边界查找、数值计算、旋转数组等常见场景，每道题都附带详细解析和Java代码，帮你巩固知识点，应对面试实战。

题目 1：LeetCode 34 在排序数组中查找元素的第一个和最后一个位置

这道题是左右边界查找的直接应用，将前面讲解的左边界、右边界函数结合起来，就能快速解题，也是面试中最常考的边界类题目之一。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        // 先判断数组为空的特殊情况，避免空指针异常
        if (nums == null || nums.length == 0) 
            return new int[]{-1, -1};

        // 调用左边界、右边界函数，获取两个边界下标
        int left = leftBound(nums, target);
        int right = rightBound(nums, target);
        // 返回结果数组，若目标值不存在，两个边界均为-1
        return new int[]{left, right};
    }

    // 左边界查找函数（复用前面的实现）
    private int leftBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        return nums[left] == target ? left : -1;
    }

    // 右边界查找函数（复用前面的实现）
    private int rightBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] > target) right = mid - 1;
            else left = mid;
        }
        return nums[left] == target ? left : -1;
    }
}

---

题目 2：LeetCode 35 搜索插入位置

这道题是左边界查找的变形，核心需求是：如果数组中存在target，返回其下标；如果不存在，返回它应该被插入的位置，保证插入后数组依然有序。解题关键是找到第一个大于等于target的位置，即为插入位置。

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1; // 目标在右侧，左边界右移
            } else {
                right = mid; // 目标在左侧或当前位置，保留mid，收缩右边界
            }
        }
        // 最后判断：若当前元素小于target，插入到当前位置后面；否则插入到当前位置
        return nums[left] < target ? left + 1 : left;
    }
}

---

题目 3：LeetCode 69 x 的平方根

这道题是二分查找在数值计算中的应用，需求是求x的算术平方根，只保留整数部分（例如：x=8，平方根是2.828，返回2）。核心思路是找到最大的整数mid，使得mid² ≤ x，这个mid就是x的算术平方根的整数部分。

class Solution {
    public int mySqrt(int x) {
        // 特殊情况处理：x<1时，算术平方根小于1，整数部分为0
        if (x < 1) return 0;
        // 搜索区间：1到x（因为1的平方根是1，x的平方根不大于x）
        long left = 1;
        long right = x;

        while (left < right) {
            // 向上取整，避免死循环（若向下取整，可能导致left无法到达right）
            long mid = left + (right - left + 1) / 2;
            if (mid * mid <= x) {
                left = mid; // mid满足条件，尝试找更大的满足条件的数
            } else {
                right = mid - 1; // mid不满足条件，缩小右边界
            }
        }
        // 循环结束后，left=right，即为x的算术平方根的整数部分
        return (int) left;
    }
}

---

题目 4：LeetCode 852 / 162 山峰数组、寻找峰值

这道题考察二分查找的核心本质——二段性，而非数组有序。山峰数组的特点是：前半部分严格递增，后半部分严格递减，峰值就是数组中最大的元素，也是递增和递减的分界点，利用这一二段性，可快速用二分找到峰值。

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        // 搜索区间：1到arr.length-2（峰值不可能在数组两端，避免越界）
        int left = 1;
        int right = arr.length - 2;

        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            // 若mid位置元素大于前一个元素，说明在递增段，峰值在右侧
            if (arr[mid] > arr[mid - 1]) {
                left = mid;
            } else {
                // 否则在递减段，峰值在左侧
                right = mid - 1;
            }
        }
        // 循环结束后，left=right，即为峰值下标
        return left;
    }
}

---

题目 5：LeetCode 153 寻找旋转排序数组中的最小值

旋转排序数组是二分查找的经典变形场景，这类数组是由有序数组旋转得到（例如：[0,1,2,4,5,6,7]旋转后得到[4,5,6,7,0,1,2]），其依然具有二段性：一部分是有序递增区间，另一部分也是有序递增区间，且前半段区间的所有元素都大于后半段区间的所有元素，利用这一特点可快速找到最小值。

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        // 以数组最右侧元素为基准，判断mid所在的区间
        int x = nums[right];

        while (left < right) {
            int mid = left + (right - left) / 2;
            // 若mid元素大于基准x，说明mid在左半段（较大元素区间），最小值在右侧
            if (nums[mid] > x) {
                left = mid + 1;
            } else {
                // 否则mid在右半段（较小元素区间），最小值在左侧或当前位置
                right = mid;
            }
        }
        // 循环结束后，left=right，即为最小值下标
        return nums[left];
    }
}

---

五、二分查找核心总结（必背）

1. 二分的本质不是有序，而是二段性：这是最核心的知识点，只要能将搜索区间明确划分为“满足条件”和“不满足条件”两部分，且两部分边界清晰，无论数组是否整体有序，都能使用二分查找。

2. 循环条件（核心区分）：

   • 找确定值（如LeetCode 704）：left <= right，需判断每一个位置的元素，避免遗漏；

   • 找边界/峰值/最小值（如左右边界、山峰数组）：left < right，循环结束后left与right重合，再判断该位置是否符合要求。

3. mid 写法（避坑关键）：

   • 向下取整：left + (right-left)/2，适用于找左边界、确定值查找等场景；

   • 向上取整：left + (right-left+1)/2，适用于找右边界、峰值等场景，避免出现死循环。

4. 区间收缩（灵活运用）：

   • 右移：left = mid + 1，当mid位置元素不满足目标条件，且目标在右侧区间时使用；

   • 左移：right = mid - 1，当mid位置元素不满足目标条件，且目标在左侧区间时使用；

   • 保留 mid：left=mid 或 right=mid，当mid位置元素可能是目标值（如边界、峰值），需要保留该位置继续查找时使用。

---

六、学习建议

1. 先把704 基础二分写熟：这是所有二分题的基础，先熟练掌握基础模板，理解循环条件、mid写法、区间收缩的逻辑，不要急于刷难题；

2. 再练34 左右边界：左右边界是二分变形的核心，多手推几遍区间变化过程，理解“向下取整/向上取整”和“保留mid”的原因，避免死记模板；

3. 然后按顺序刷题：35（插入位置）→ 69（平方根）→ 852（山峰数组）→ 153（旋转数组最小值）→ 162（寻找峰值），循序渐进，巩固不同场景的应用；

4. 每道题自己手推一遍区间变化，不要死记模板：二分的难点在于边界处理，手推区间变化（如left、right、mid的每次取值），能快速理解收缩逻辑，避免出错。

最后提醒：二分查找看似简单，实则细节为王，很多人刷题时出错，不是不会模板，而是忽略了边界条件和区间收缩的细节。只要理解区间怎么缩，掌握二段性的核心，所有二分题都是换汤不换药，多练、多推、多总结，就能轻松应对面试中的各类二分考点。