二分查找

循环

public static int binarySearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int middle = (low + high) / 2;
            if (key == arr[middle]) {
                return middle;
            } else if (key < arr[middle]) {
                high = middle - 1;
            } else {
                low = middle + 1;
            }
        }
        return -1;
    }

递归

public static int binarySearch(int[] arr, int key, int beginIndex, int endIndex) {
        int middleIndex = (beginIndex + endIndex) / 2;
        if (key< arr[beginIndex] || key> arr[endIndex] || beginIndex > endIndex) {
            return 0;
        }
        if (key< arr[middleIndex]) {
            return binarySearch(arr, key, beginIndex, middleIndex - 1);
        } else if (key> arr[middleIndex]) {
            return binarySearch(arr, key, middleIndex + 1, endIndex);
        } else {
            return middleIndex;
        }
    }