note/algorithm/4、时间复杂度.md

二分法问题

• 有序数组中找到num
• 有序数组中找到>=num最左的位置
• 有序数组中找到<=num最右的位置
• 局部最小值问题

使用while循环，根据target在middle的位置，移动left或者right。

private static int binarySearch(int[] arr, int target) {
    if (arr == null || arr.length == 0) {
        return -1;
    }
    int length = arr.length;
    int left = 0;
    int right = length-1;
    int index = -1;
    int middle;
    while (left <= right) {
        middle = left + ((right-left) >> 1);
        if (arr[middle] == target) {
            index = middle;
            return index;
        } else if (arr[middle] < target) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    return index;
}

// 大于等于target最左的位置
private static int binarySearchLeft(int[] arr, int target) {
    if (arr == null || arr.length == 0) {
        return -1;
    }
    int length = arr.length;
    int left = 0;
    int right = length-1;
    int index = -1;
    int middle;
    while (left <= right) {
        middle = left + ((right-left) >> 1);
        if (arr[middle] >= target) {
            index = middle;
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }
    return index;
}

// 小于等于target最右的位置
private static int binarySearchRight(int[] arr, int target) {
    if (arr == null || arr.length == 0) {
        return -1;
    }
    int length = arr.length;
    int left = 0;
    int right = length-1;
    int index = -1;
    int middle;
    while (left <= right) {
        middle = left + ((right-left) >> 1);
        if (arr[middle] <= target) {
            index = middle;
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    return index;
}

有序数组给定区间元素的个数，二分查找上下限，然后index取差值。

局部最小值 对无重复元素的无序数组，找出一个局部最小值。 只需要找出一个存在的局部最小值，不是全部的局部最小值，也不是全局最小值。

public int localMin(int[] arr){
    if (arr == null || arr.length == 0) {
        return -1;
    }
    int length = arr.length;
    if (length == 1) {
        return 0;
    }
    if (arr[length - 1] < arr[length - 2]) {
        return length - 1;
    }
    int left = 0;
    int right = length - 1;
    int index = -1;
    int middle;
    while (left <= right) {
        // 避免溢出
        middle = left + ((right-left) >> 1);
        if (arr[middle - 1] < arr[middle]) {
            right = middle - 1;
        } else if (arr[middle + 1] < arr[middle]) {
            left = middle + 1;
        } else {
            index = middle;
            break;
        }
    }
    return index;
}

可以确定要寻找的元素在一侧必定存在则可以使用二分搜索。

时间复杂度