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

二分查找看这篇就够了Java 版超详细讲解高频题解大家好今天我们来彻底吃透二分查找。作为算法面试、笔试中的“常青树”它是必考且基础的核心知识点看似只有“左右指针中间值对比”这一个简单逻辑但实际应用中边界处理、区间收缩、题型变形等细节极易出错很多人刷题时常常陷入死循环或边界遗漏的困境。今天我会用Java 语言从基础原理入手拆解标准模板再结合LeetCode高频真题实战演练一步步带你吃透二分查找轻松应对各类面试考点。一、什么是二分查找二分查找又称折半查找是一种高效的查找算法其核心适用前提有两个一是数组必须有序升序或降序均可本文默认以升序为例二是数组中无重复元素有重复元素的场景会在后续边界查找中专门讲解。核心思想通俗解读每次查找时将当前的搜索区间一分为二锁定中间位置的元素以此为基准进行判断通过中间元素与目标值的大小对比直接舍弃不可能包含目标值的一半区间无需逐一遍历仅在剩下的另一半区间中继续重复“分半-判断-舍弃”的流程直到找到目标值或确定目标值不存在时间复杂度为O(log n)n为数组长度相较于暴力查找的O(n)效率提升极为明显尤其在数据量较大如n10000时差距会格外突出。一句话总结有单调性就可以二分。这里的单调性不仅指数组整体有序只要能将搜索区间划分为“满足条件”和“不满足条件”两部分且两部分边界清晰就能用二分思想解题。二、最基础模板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; // 防止溢出替代(leftright)/2 if (nums[mid] target) { return mid; // 找到目标值直接返回下标 } else if (nums[mid] target) { left mid 1; // 目标值在右侧区间缩小左边界 } else { right mid - 1; // 目标值在左侧区间缩小右边界 } } return -1; // 循环结束仍未找到返回-1 } }关键点避坑重点循环条件 left right这里必须包含“等于”因为当left和right重合时当前位置的元素还未被判断若漏掉“等于”会导致该位置的目标值被遗漏出现查找失败的错误。mid 不要写成 (leftright)/2当left和right均为较大的整数如接近int类型的最大值时两者相加会超出int类型的取值范围导致数值溢出进而出现计算错误而left (right - left)/2 等价于 (leftright)/2却能有效避免溢出问题。区间更新必须是mid1/mid-1否则会死循环因为当nums[mid]不等于target时该位置已被排除若仅更新为leftmid或rightmid会导致区间无法缩小陷入无限循环例如left1、right2mid1若nums[mid]targetleft仍设为1区间始终不变。三、二分最重要的能力找边界在实际面试中单纯查找目标值的基础题占比极低更多的是变形题——找左边界、右边界、插入位置这类题目核心考察对区间收缩的精准控制也是二分查找的难点所在掌握这部分就能应对80%的二分变形题。1. 找左边界第一个等于 target 的位置适用场景数组中存在重复元素需要找到目标值第一次出现的位置例如数组[1,2,2,2,3]target2左边界为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 } } // 循环结束后leftright判断该位置是否为目标值 return nums[left] target ? left : -1; }2. 找右边界最后一个等于 target 的位置适用场景数组中存在重复元素需要找到目标值最后一次出现的位置例如数组[1,2,2,2,3]target2右边界为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 } } // 循环结束后leftright判断该位置是否为目标值 return nums[left] target ? left : -1; }记忆口诀快速掌握避免混淆找左边界mid 向下取整rightmid优先收缩右边界保留左侧可能的边界找右边界mid 向上取整leftmid优先收缩左边界保留右侧可能的边界循环条件一律用left right循环结束后left与right重合再判断是否为目标值避免边界遗漏。四、LeetCode 高频真题Java 版理论结合实战才是掌握二分的关键下面精选5道LeetCode高频真题覆盖边界查找、数值计算、旋转数组等常见场景每道题都附带详细解析和Java代码帮你巩固知识点应对面试实战。题目 1LeetCode 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; } }题目 2LeetCode 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; } }题目 3LeetCode 69 x 的平方根这道题是二分查找在数值计算中的应用需求是求x的算术平方根只保留整数部分例如x8平方根是2.828返回2。核心思路是找到最大的整数mid使得mid² ≤ x这个mid就是x的算术平方根的整数部分。class Solution { public int mySqrt(int x) { // 特殊情况处理x1时算术平方根小于1整数部分为0 if (x 1) return 0; // 搜索区间1到x因为1的平方根是1x的平方根不大于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不满足条件缩小右边界 } } // 循环结束后leftright即为x的算术平方根的整数部分 return (int) left; } }题目 4LeetCode 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; } } // 循环结束后leftright即为峰值下标 return left; } }题目 5LeetCode 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; } } // 循环结束后leftright即为最小值下标 return nums[left]; } }五、二分查找核心总结必背二分的本质不是有序而是二段性这是最核心的知识点只要能将搜索区间明确划分为“满足条件”和“不满足条件”两部分且两部分边界清晰无论数组是否整体有序都能使用二分查找。循环条件核心区分找确定值如LeetCode 704left right需判断每一个位置的元素避免遗漏找边界/峰值/最小值如左右边界、山峰数组left right循环结束后left与right重合再判断该位置是否符合要求。mid 写法避坑关键向下取整left (right-left)/2适用于找左边界、确定值查找等场景向上取整left (right-left1)/2适用于找右边界、峰值等场景避免出现死循环。区间收缩灵活运用右移left mid 1当mid位置元素不满足目标条件且目标在右侧区间时使用左移right mid - 1当mid位置元素不满足目标条件且目标在左侧区间时使用保留 midleftmid或rightmid当mid位置元素可能是目标值如边界、峰值需要保留该位置继续查找时使用。六、学习建议先把704 基础二分写熟这是所有二分题的基础先熟练掌握基础模板理解循环条件、mid写法、区间收缩的逻辑不要急于刷难题再练34 左右边界左右边界是二分变形的核心多手推几遍区间变化过程理解“向下取整/向上取整”和“保留mid”的原因避免死记模板然后按顺序刷题35插入位置→ 69平方根→ 852山峰数组→ 153旋转数组最小值→ 162寻找峰值循序渐进巩固不同场景的应用每道题自己手推一遍区间变化不要死记模板二分的难点在于边界处理手推区间变化如left、right、mid的每次取值能快速理解收缩逻辑避免出错。最后提醒二分查找看似简单实则细节为王很多人刷题时出错不是不会模板而是忽略了边界条件和区间收缩的细节。只要理解区间怎么缩掌握二段性的核心所有二分题都是换汤不换药多练、多推、多总结就能轻松应对面试中的各类二分考点。