前提说明二分查找折半查找只能作用于有序数组 核心思想不断缩小查找区间每次用中间元素和目标值对比排除一半区间时间复杂度 \(O(logn)\)顺序查找是 \(O(n)\)。算法思路定义左右边界left 0数组起始下标right arr.length - 1数组末尾下标循环条件left right区间内还有元素可以比较计算中间下标mid推荐写法mid left (right - left) / 2防止(leftright)数值溢出三种情况判断arr[mid] target找到目标返回 mid 索引arr[mid] target目标在右半区更新左边界left mid 1arr[mid] target目标在左半区更新右边界right mid - 1循环结束仍未找到返回 -1代表不存在⚠️ 注意边界mid1/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) { // 计算中间索引避免 leftright 溢出 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使用时需要留意判断逻辑。
Java 二分查找实现（附完整思路）
前提说明二分查找折半查找只能作用于有序数组 核心思想不断缩小查找区间每次用中间元素和目标值对比排除一半区间时间复杂度 \(O(logn)\)顺序查找是 \(O(n)\)。算法思路定义左右边界left 0数组起始下标right arr.length - 1数组末尾下标循环条件left right区间内还有元素可以比较计算中间下标mid推荐写法mid left (right - left) / 2防止(leftright)数值溢出三种情况判断arr[mid] target找到目标返回 mid 索引arr[mid] target目标在右半区更新左边界left mid 1arr[mid] target目标在左半区更新右边界right mid - 1循环结束仍未找到返回 -1代表不存在⚠️ 注意边界mid1/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) { // 计算中间索引避免 leftright 溢出 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使用时需要留意判断逻辑。
