本文共 3743 字，大约阅读时间需要 12 分钟。
二分查找是一种高效的查找算法，能够在有序数组中快速定位特定元素。其时间复杂度为 O(log n)，因为每次搜索都会将问题规模缩小一半，从而在 logarithmic 时间内完成搜索。
二分查找可以通过递归或非递归方式实现。以下是两种实现方式的代码示例：
import java.util.Arrays;public class BinarySearch { public static void main(String[] args) { int[] ints = { -30, -30, -15, -2, 0, 2, 2, 2, 2, 7, 8, 13, 22, 27, 99, 99, 100, 333, 666, 999 }; int key = 2; System.out.println("数组：" + Arrays.toString(ints)); System.out.println("递归查找：\t数字" + key + "在数组中下标为" + binarySearch(ints, key, true)); System.out.println("非递归查找：\t数字" + key + "在数组中下标为" + binarySearch(ints, key, false)); } private static int binarySearch(int[] ints, int key, boolean recursion) { if (ints == null || ints.length == 0) { return -1; } if (recursion) { return binarySearch(ints, 0, ints.length - 1, key); } else { return binarySearch(ints, key); } } private static int binarySearch(int[] ints, int key) { int from = 0; int to = ints.length; while (from < to) { int mid = from + (to - from) / 2; if (ints[mid] > key) { to = mid - 1; } else if (ints[mid] < key) { from = mid + 1; } else { return mid; } } return -1; } private static int binarySearch(int[] ints, int from, int to, int key) { int mid = from + (to - from) / 2; if (ints[mid] == key) { return mid; } if (from >= to) { return -1; } if (ints[mid] > key) { return binarySearch(ints, from, mid - 1, key); } else { return binarySearch(ints, mid + 1, to, key); } }} 代码与递归实现的主要区别在于查找过程中没有使用递归函数，而是通过循环实现的逻辑。
运行以下命令进行测试：
D:\program\Java\jdk1.8.0_241\bin\java.exe -agentlib:jdwp=transport=dt_socket,address=127.0.0.1:63454,suspend=y,server=n "-javaagent:C:\Users\GMWANG~1\AppData\Local\Temp\captureAgent8jars\debugger-agent.jar" -Dfile.encoding=UTF-8 -classpath "D:\program\Java\jdk1.8.0_241\jre\lib\charsets.jar;D:\program\Java\jdk1.8.0_241\jre\lib\deploy.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\access-bridge-64.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\cldrdata.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\dnsns.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\jaccess.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\jfxrt.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\localedata.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\nashorn.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\sunec.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\sunjce_provider.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\sunmscapi.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\sunpkcs11.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\zipfs.jar;D:\program\Java\jdk1.8.0_241\jre\lib\javaws.jar;D:\program\Java\jdk1.8.0_241\jre\lib\jce.jar;D:\program\Java\jdk1.8.0_241\jre\lib\jfr.jar;D:\program\Java\jdk1.8.0_241\jre\lib\jfxswt.jar;D:\program\Java\jdk1.8.0_241\jre\lib\jsse.jar;D:\program\Java\jdk1.8.0_241\jre\lib\management-agent.jar;D:\program\Java\jdk1.8.0_241\jre\lib\plugin.jar;D:\program\Java\jdk1.8.0_241\jre\lib\resources.jar;D:\program\Java\jdk1.8.0_241\jre\lib\rt.jar;D:\project\untitled\out\production\untitled;D:\program\JetBrains\IntelliJ IDEA 2020.1\lib\idea_rt.jar" BinarySearchConnected to the target VM, address: '127.0.0.1:63454', transport: 'socket'数组：[-30, -30, -15, -2, 0, 2, 2, 2, 2, 7, 8, 13, 22, 27, 99, 99, 100, 333, 666, 999]递归查找： 数字2在数组中下标为6非递归查找： 数字2在数组中下标为7Disconnected from the target VM, address: '127.0.0.1:63454', transport: 'socket'Process finished with exit code 0
测试结果显示，递归查找和非递归查找均成功找到数字 2 的位置，分别返回了下标 6 和 7。
转载地址：http://oqxwz.baihongyu.com/