当前位置：首页 > news >正文

Java 二分查找实现（附完整思路）

news 2026/7/23 13:11:18

前提说明

二分查找（折半查找）只能作用于有序数组！核心思想：不断缩小查找区间，每次用中间元素和目标值对比，排除一半区间，时间复杂度 \(O(logn)\)；顺序查找是 \(O(n)\)。

算法思路

定义左右边界：left = 0（数组起始下标），right = arr.length - 1（数组末尾下标）
循环条件：left <= right，区间内还有元素可以比较
计算中间下标mid，推荐写法mid = left + (right - left) / 2，防止(left+right)数值溢出
三种情况判断：
- arr[mid] == target：找到目标，返回 mid 索引
- arr[mid] < target：目标在右半区，更新左边界left = mid + 1
- arr[mid] > target：目标在左半区，更新右边界right = mid - 1
循环结束仍未找到，返回 -1（代表不存在）

⚠️ 注意边界：mid+1/mid-1，不要重复比较 mid 位置元素，否则容易死循环。

方式 1：迭代实现（日常开发最常用）

java

运行

public class BinarySearch { /** * 二分查找 迭代版 * @param arr 有序升序数组 * @param target 要查找的值 * @return 找到返回下标，找不到返回 -1 */ public static int binarySearch(int[] arr, int target) { // 1. 初始化左右指针 int left = 0; int right = arr.length - 1; // 2. [left, right] 闭区间，left <= right 区间有效 while (left <= right) { // 计算中间索引，避免 left+right 溢出 int mid = left + (right - left) / 2; if (arr[mid] == target) { // 3. 找到目标，直接返回下标 return mid; } else if (arr[mid] < target) { // 目标在右侧，左边界右移，mid已经比较过，+1 left = mid + 1; } else { // 目标在左侧，右边界左移 right = mid - 1; } } // 循环结束没有找到 return -1; } public static void main(String[] args) { int[] sortedArr = {1, 3, 5, 7, 9, 11, 13}; int target1 = 7; int target2 = 4; int index1 = binarySearch(sortedArr, target1); int index2 = binarySearch(sortedArr, target2); System.out.println(target1 + " 下标：" + index1); System.out.println(target2 + " 下标：" + index2); } }

方式 2：递归实现（适合理解思想，工程慎用，大数据量会栈溢出）

java

运行

public class BinarySearchRecursion { public static int binarySearch(int[] arr, int left, int right, int target) { // 递归终止条件：区间不存在 if (left > right) { return -1; } int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { // 去右区间递归查找 return binarySearch(arr, mid + 1, right, target); } else { // 去左区间递归查找 return binarySearch(arr, left, mid - 1, target); } } public static void main(String[] args) { int[] arr = {2, 4, 6, 8, 10, 12}; int res = binarySearch(arr, 0, arr.length - 1, 8); System.out.println("索引 = " + res); } }

常见易错点总结

数组必须有序，无序数组不能直接二分查找；
mid = (left + right) / 2当 left、right 很大时会整数溢出，优先left + (right-left)/2；
区间定义：本例是闭区间 [left, right]，所以循环条件left <= right，边界更新mid±1；如果写成左闭右开[left, right)，循环条件和边界赋值写法需要改动；
如果数组存在重复元素，该代码只会返回任意一个匹配下标，不能保证第一个 / 最后一个；想要查找左边界、右边界，需要改造逻辑。

扩展：JDK 自带二分方法

Arrays.binarySearch()

java

运行

import java.util.Arrays; public class Test { public static void main(String[] args) { int[] arr = {1,2,3,4,5}; int idx = Arrays.binarySearch(arr, 3); System.out.println(idx); } }