Binary Search - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

入门链接

【老九学堂】二分查找法 LeetCode算法实战:十分钟彻底搞懂二分查找

图解

详解

二分查找有几种写法?它们的区别是什么? 详解二分查找算法 如何正确的理解循环不变式? 循环不变式的理解

标准写法

步骤1:选中位数

median = low + (high - low) / 2;

步骤2:终止条件Base Case

  • 不要以 low == high 做终结条件,否则会被跳过
  • 正确的终结条件是:low > high 也就是搜索空间为空
  • 满足终结条件以后,返回值完全不需要纠结,直接返回低位 low
  • 递归版
if (low > high) {
    return low;
}
int mid = low + (high - low) / 2;
...
  • 非递归版
int low = 0, high = nums.length - 1;
while (low <= high) {
    int mid = low + (high - low) / 2;
    ...
    return low;
}

步骤3:完成

  • 递归版
public static int binarySearch(int[] nums, int target, int low, int high) { 
    if (low > high) {
        return low;
    }
    int mid = low + (high - low) / 2;
    if (nums[mid] < target) {
        return binarySearch(nums, target, mid + 1, high);
    } else {
        return binarySearch(nums, target, low, mid - 1);
    }
}
  • 非递归版
public static int binarySearch(int[] nums, int target) { 
    int low = 0, high = nums.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] < target) {
            low = mid + 1;
        } else { 
            high = mid - 1;
        }
        return low;
}

场景分析:Tutorial分配

题目

  1. 学生有想要的Tutorial
  2. 每个Tutorial的学生人数不可以超过15人

解答

  • MaxStudents(x) = 如果我们提供x个Tutorials,则返回最多学生的Tutorials中的学生人数
  • 假设MaxStudents(x)已经实现,则只需要通过二分搜索找到最适合的Tutorials的数量即可
  • 输入当前可以分配的最大的Tutorials的数量n
public static int search(int n) {
    begin = 0;
    end = n - 1;
    while begin < end
        mid = begin + (end - begin) / 2;
        if MaxStudents(mid) <= 15
            end = mid;
        else 
            begin = mid + 1;
    return begin;
}

要点

  • 函数输出Functionality
    • 若元素在数组中,则返回元素的索引
    • 若元素不在数组中,返回-1
  • 先决条件Precondition
    • 数组必须是有序的
    • 必须知道数组的大小
  • 后置条件Postcondition
    • 若目标元素存在于数组中,则有 arr[low] = target
  • 循环不变式Loop Invariant
    • arr[low] <= target <= arr[high]
  • 解释Interpretation
    • target在数组范围内
  • 错误检查
    if ((A[begin] > key) or (A[end] < key)) {
        System.out.println(“error”);
    }