Java二分查找（笔记、（25））

在 Java 中二分查找Binary Search是一种在有序数组中快速查找目标值的算法。它的核心思想是每次将查找范围缩小一半时间复杂度为O(log n)相比顺序查找的 O(n) 效率高很多。下面我会从原理、迭代实现、递归实现、使用Arrays.binarySearch()以及注意事项几个方面来讲解。原理简述假设有一个升序排列的数组arr要查找目标值target初始化左指针left 0右指针right arr.length - 1。循环直到left right计算中间位置mid left (right - left) / 2防止溢出。如果arr[mid] target返回mid。如果arr[mid] target说明目标在右半部分left mid 1。如果arr[mid] target说明目标在左半部分right mid - 1。循环结束仍未找到返回-1表示不存在。方式一、迭代实现最常用package cn; import java.util.*; import java.io.*; public class text_22_BinarySearch { static PrintWriter out new PrintWriter(System.out); public static void main(String[] args) throws IOException { // TODO Auto-generated method stub //二分查找 数组必须是有序且升序的 Integer arr[] {2,9,3,6,0,1,4,8,7,5}; //数组排序lamda表达式格式排序 Arrays.sort(arr,(x,y) - x - y); out.println(Arrays.toString(arr)); out.flush(); binarySearch(arr,3); } public static int binarySearch(Integer arr[],int num) { //定义最小索引 int minIndex 0; //定义最大索引 int maxIndex arr.length - 1; //定义中间索引 int midIndex 0; while(minIndex maxIndex) { midIndex (minIndex maxIndex) / 2; if(arr[midIndex] num) { maxIndex midIndex - 1; } else if(arr[midIndex] num) { minIndex midIndex 1; } else if(arr[midIndex] num) { break; } } if(minIndex maxIndex) { out.print(num 该值数组中不存在); out.flush(); } else { out.print(num 该值在数组中的位置为 (midIndex 1) ,索引为 midIndex); out.flush(); } return midIndex; } }方式二、使用 Java 内置的Arrays.binarySearch()import java.util.Arrays; public class BuiltInBinarySearch { public static void main(String[] args) { int[] arr {2, 5, 8, 12, 16, 23, 38, 45, 56, 72}; int target 38; int index Arrays.binarySearch(arr, target); System.out.println(target 的索引是 index); // 输出 6 // 如果找不到返回 (-(插入点) - 1) int notExist Arrays.binarySearch(arr, 100); System.out.println(notExist); // 输出 -11 } }