前提说明
二分查找（折半查找）只能作用于有序数组！ 核心思想：不断缩小查找区间，每次用中间元素和目标值对比，排除一半区间，时间复杂度 \(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 + 1arr[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); } }找不到时不会返回 - 1，返回
-(插入点)-1，使用时需要留意判断逻辑。