二分法

时间复杂度

• O(1) 极少
• O(logn) 几乎都是二分法
• O(√n) 几乎是分解质因数
• O(n) 高频
• O(nlogn) 一般都可能要排序
• O(n^2) 数组，枚举，动态规划
• O(n^3) 数组，枚举，动态规划
• O(2^n) 与组合有关的搜索
• O(n!) 与排列有关的搜索

递归与非递归

• 不用递归是否造成实现的复杂
• 递归的深度是否很深

二分法通用模板

• 可扩展于寻找target第一次出现的位置，最后一次出现的位置

public class BinarySearch {
    /**
     * @param nums: The integer array sorted in ascending order.
     * @param target: Target to find.
     * @return: The position of target.
     */
    public int binarySearch(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0, end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return nums[mid];
            } else if (nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (nums[start] == target) return start;
        else if (nums[end] == target) return end;
        else return -1;
    }
}

• 标准迭代

public int runBinarySearchIteratively(
  int[] sortedArray, int key, int low, int high) {
    int index = Integer.MAX_VALUE;
     
    while (low <= high) {
        int mid = (low + high) / 2;
        if (sortedArray[mid] < key) {
            low = mid + 1;
        } else if (sortedArray[mid] > key) {
            high = mid - 1;
        } else if (sortedArray[mid] == key) {
            index = mid;
            break;
        }
    }
    return index;
}

• 标准递归

public int runBinarySearchRecursively(
  int[] sortedArray, int key, int low, int high) {
    int middle = (low + high) / 2;
         
    if (high < low) {
        return -1;
    }
 
    if (key == sortedArray[middle]) {
        return middle;
    } else if (key < sortedArray[middle]) {
        return runBinarySearchRecursively(
          sortedArray, key, low, middle - 1);
    } else {
        return runBinarySearchRecursively(
          sortedArray, key, middle + 1, high);
    }
}