本文共 3689 字，大约阅读时间需要 12 分钟。

1 原理

时间复杂度为O(logn)。

2 实现

import java.util.Arrays;/** * 二分查找算法 * * @author wgm * @since 2021/4/18 */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));    }    /**     * 二分查找（递归/非递归）     *     * @param ints     * @param key     * @param recursion     * @return     */    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);        }    }}

3 测试

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