[数据结构与算法]算法学习之二分法碎碎念

简述

今晚来写写二分查找的一些所思所想所得，文章错漏之处还请各位指出，感激不尽！

搞懂二分查找，需要搞懂以下几部分的真正含义：

1. while循环中 left < high / left <= high 含义是什么，怎么选出合适的循环条件？

2. mid 与 target 之间的大小关系在何时需要带=号？

3. left = mid + 1？right = mid - 1？缩小范围时具体采取什么样的策略？

坦白来说，提出以上几点疑问的缘由是做题过程中反复在上述几个点上碰壁，最后来回调试才得以解题，就二分查找而言，其核心含义在于在一个有序的空间中于每轮排除一半的搜索范围，不断缩小搜索空间最终返回题解，由于这类题目套路满满，因此诞生了几种做题模板。

模板

LeetCode二分查找专栏提供的三类模板如下：

第一种

int binarySearch(int[] nums, int target){
  if(nums == null || nums.length == 0)
    return -1;

  int left = 0, right = nums.length - 1;
  while(left <= right){
    // Prevent (left + right) overflow
    int mid = left + (right - left) / 2;
    if(nums[mid] == target){ return mid; }
    else if(nums[mid] < target) { left = mid + 1; }
    else { right = mid - 1; }
  }

  // End Condition: left > right
  return -1;
}

基于第一种模板的经典题目有：NO 374 猜数字大小、NO 33 搜索旋转排序数组

第二种

int binarySearch(int[] nums, int target){
  if(nums == null || nums.length == 0)
    return -1;

  int left = 0, right = nums.length;
  while(left < right){
    // Prevent (left + right) overflow
    int mid = left + (right - left) / 2;
    if(nums[mid] == target){ return mid; }
    else if(nums[mid] < target) { left = mid + 1; }
    else { right = mid; }
  }

  // Post-processing:
  // End Condition: left == right
  if(left != nums.length && nums[left] == target) return left;
  return -1;
}

第三种

int binarySearch(int[] nums, int target) {
    if (nums == null || nums.length == 0)
        return -1;

    int left = 0, right = nums.length - 1;
    while (left + 1 < right){
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid;
        } else {
            right = mid;
        }
    }

    // Post-processing:
    // End Condition: left + 1 == right
    if(nums[left] == target) return left;
    if(nums[right] == target) return right;
    return -1;
}

碎碎念式总结

把LeetCode二分查找的几道配套习题做完了，说说自己的几点体会（下列说法的假设为题目给定的nums数组非递减）：

1. 具体怎么使用二分法关键在于题意（废话），根据题意打草稿很重要，简述中提到的几个问题关键便在于依据题意灵活应变（希望后期能进一步参悟二分法，回来补补这块）；

2. while() 中的条件可不可以写 left <= right ？

   • 是否需要考虑 left == right == middle 的情况？是否能接受出现 left == right == middle 后 left = middle + 1 或者 right = middle - 1 或者某个 break 条件来跳出循环？（某些题目需要 left / right 返回目标答案，这么做是否会破坏答案）

3. 返回目标值采用循环内break还是等待循环结束？

   • 循环内break的经典案例为：

     if (nums[middle] == target) {
         ans = middle;
         break;
     }

     等待循环结束返回的经典案例为：

     while(left < right) {
         if (nums[left] < target) {
             // 这里不写等号，因为我们并不希望left跳过我们希望的答案
             left = middle + 1;
         } else {
             right = middle;
         }
     }
     return nums[left];

     关于上述两种返回策略的选择，考虑的点在于target值是否唯一 && 题目需要返回数组中值为target的某一端？以具体题目为例：

     1. LeetCode 278 第一个错误的版本：题意希望函数能够返回第一个错误的版本，若函数采取找到任一错误的版本即循环内break的方案，那么后续还需要往前找第一个错误版本，吃力不讨好。在此选择循环结束返回的方案就比较合适；

     2. LeetCode 704 二分查找：这道题是较为基础的一道关于二分查找的题目，本题中采用上述两种返回方案其实都可以，题意并没有要求我们返回第一个 or 最后一个目标值。